#P18383. Ring of Beads

Ring of Beads

Ring of Beads

题目描述

有 nn 颗珠子按顺时针方向排成一圈,编号为 1,2,…,n1,2,\ldots,n。每颗珠子可以被染成青色或白色。

对任意 1≤l,r≤n1\le l,r\le n,定义顺时针闭区间 I(l,r)I(l,r):

  • 若 l≤rl\le r,包含编号 l,l+1,…,rl,l+1,\ldots,r 的珠子。
  • 若 l>rl>r,包含编号 l,l+1,…,n,1,2,…,rl,l+1,\ldots,n,1,2,\ldots,r 的珠子。

用 S(l,r)S(l,r) 表示 I(l,r)I(l,r) 内青色珠子的数量。

现在给出 mm 条限制,每条限制由四元组 (t,l,r,v)(t,l,r,v) 表示:

  • t=1t=1:要求 S(l,r)≥vS(l,r)\ge v。
  • t=2t=2:要求 S(l,r)≤vS(l,r)\le v。
  • t=3t=3:要求 S(l,r)=vS(l,r)=v。

首先判断是否存在满足全部限制的染色方案。若存在,求有多少个区间 I(l,r)I(l,r) 的青色珠子数在所有合法染色方案中都相同。不同区间的固定数值不需要相同。

两个区间 I(l1,r1)I(l_1,r_1) 与 I(l2,r2)I(l_2,r_2) 不同,当且仅当 l1≠l2l_1\ne l_2 或 r1≠r2r_1\ne r_2。特别地,虽然

I(1,n),I(2,1),I(3,2),…,I(n,n−1)I(1,n),I(2,1),I(3,2),\ldots,I(n,n-1)

都包含整个圆环,它们仍然是 nn 个不同区间。共有 n2n^2 个待统计的有序端点区间。

输入格式

第一行包含两个整数 n,mn,m(2≤n≤1092\le n\le10^9,1≤m≤10001\le m\le1000)。

接下来 mm 行,每行包含四个整数 t,l,r,vt,l,r,v,其中 t∈{1,2,3}t\in\{1,2,3\},1≤l,r≤n1\le l,r\le n,0≤v≤L0\le v\le L,L=∣I(l,r)∣L=|I(l,r)| 为该区间内珠子的数量。

本题输入只有一组数据。

输出格式

若不存在合法染色方案,输出一行一个整数 −1-1。

否则输出一行一个整数,表示青色珠子数在所有合法染色中保持不变的区间数量。

样例输入 1

16 8
1 1 3 1
1 5 7 1
1 9 11 1
1 13 15 1
2 2 6 1
2 6 10 1
2 10 14 1
2 14 2 1

样例输出 1

128

样例输入 2

1000000000 1
2 114514 114513 0

样例输出 2

1000000000000000000

样例输入 3

100 3
3 1 10 1
3 91 100 1
3 81 20 2

样例输出 3

253

样例输入 4

6 3
1 1 3 2
1 4 6 2
2 2 5 1

样例输出 4

-1

样例说明

第一组样例只有两种合法染色,C 表示青色,W 表示白色:

CWWWCWWWCWWWCWWW
WWCWWWCWWWCWWWCW

恰好有 16216^2 个区间中的一半,即 128128 个区间,在两种染色中包含相同数量的青色珠子。

第二组样例中的区间覆盖整个圆环,限制要求没有青色珠子,因此唯一合法染色是全部为白色;所有 n2n^2 个区间都应计入答案。