本文共 17601 字，大约阅读时间需要 58 分钟。

写在前面

想必大家都有了一定的线段树基础，所以来做点更有意思的线段树吧（

CF803G Periodic RMQ Problem

先来道黑题热热身

Description

题面：

给你一个序列 \(a\) 让你支持: 区间赋值;询问区间最小值

我们觉得这个问题太水了,所以我们不会给你序列 \(a\)

而是给你序列一个长度为 \(n\) 的序列 \(b\) ,把 \(b\) 复制粘贴 \(k\) 次就可以得到 \(a\)

\(n \le 10^5,k \le 10^4,q \le 10^5,b_i \le 10^9\)

\(1 \le l \le r \le n \times k\)

Solution

维护的线段树操作不难，麻烦的地方在于对原序列的处理，理解思想后完全可以自己yy出代码。

看到 “区间覆盖，区间最小值” ，这不板子？

但是，序列长度可是 \(n \times k = 10^9\) 啊。

发现询问涉及到的点只有 \(10^5\) 级别，考虑进行离散化处理，只保留对答案有贡献的信息。

注意：对答案有贡献的信息不仅仅是询问涉及到的点，还有相邻的两个涉及到的点的区间也对答案有贡献

（因为这个区间内的最小值可能比两个端点更小）。

蓝色箭头是询问涉及过的点，相邻的两个涉及过的点的区间被压缩成一个点来处理（如果相邻两个涉及过的点之间没有区间就不压缩）。

把这两种点都放进一个新的序列（红色序列），然后在新的序列上进行修改查询操作即可。

注意映射好询问涉及到的点在红色序列中的位置。

注意将区间压缩成一个点时的处理：

• 如果区间长度超过 \(n\)，直接加入原来整段区间的最小值（但是数据没卡这个地方）
• 如果在同一个区间内，加入这个区间内的最小值
• 如果跨越了两个区间，加入区间 \([1, r]\) 和 \([l, n]\) 的最小值

这种做法在复杂度和空间消耗上都比较优秀。

剩下的看代码吧，重要步骤都有注释，如果有不懂的也可以在评论区提出

Code

/*Work by: Suzt_ilymicsKnowledge: ??Time: O(??)*/#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define LL long long#define orz cout<<"lkp AK IOI!"<
        
         << 1) + (s << 3) + ch - '0' , ch = getchar(); return f ? -s : s;}struct Big_Seg{ // 采用结构体，码量会更少哦 #define lson i << 1 #define rson i << 1 | 1 struct Tree{ int min, lazy; }tree[MAXN << 3]; void Push_up(int i) { tree[i].min = min(tree[lson].min, tree[rson].min); } void Push_down(int i) { if(tree[i].lazy) { tree[lson].lazy = tree[rson].lazy = tree[i].lazy; tree[lson].min = tree[rson].min = tree[i].lazy; tree[i].lazy = 0; } } void Build(int i, int l, int r) { //两个建树分别给两个线段树用 if(l == r) { tree[i].min = b[l]; return ; } int mid = (l + r) >> 1; Build(lson, l, mid), Build(rson, mid + 1, r); Push_up(i); } void Build0(int i, int l, int r) { if(l == r) { tree[i].min = a[l]; return ; } int mid = (l + r) >> 1; Build0(lson, l, mid), Build0(rson, mid + 1, r); Push_up(i); } void Change(int i, int l, int r, int L, int R, int k) { if(L <= l && r <= R) { tree[i].min = tree[i].lazy = k; return ; } Push_down(i); int mid = (l + r) >> 1; if(mid >= L) Change(lson, l, mid, L, R, k); if(mid < R) Change(rson, mid + 1, r, L, R, k); Push_up(i); } int Get_min(int i, int l, int r, int L, int R) { if(L <= l && r <= R) return tree[i].min; Push_down(i); int mid = (l + r) >> 1, ans = INF; if(mid >= L) ans = min(ans, Get_min(lson, l, mid, L, R)); if(mid < R) ans = min(ans, Get_min(rson, mid + 1, r, L, R)); return ans; }}Seg[2];int main(){ n = read(), K = read(); for(int i = 1; i <= n; ++i) a[i] = read(); Seg[0].Build0(1, 1, n); // 先对给定的小序列建树 m = read(); for(int i = 1; i <= m; ++i) { q[i].opt = read(), q[i].l = read(), q[i].r = read(); date[++ cnt] = q[i].l, date[++ cnt] = q[i].r; if(q[i].opt == 1) q[i].val = read(); } sort(date + 1, date + cnt + 1); date[0] = -INF; for(int i = 1; i <= cnt; ++i) if(date[i] != date[i - 1]) date[++ date_num] = date[i]; // 离散化 //一下是构造新序列b过程（即图中的红色序列 for(int i = 1; i < date_num; ++i) { if(date[i] % n == 0) b[++Cnt] = a[n]; else b[++Cnt] = a[date[i] % n]; pre[i] = Cnt; // 进行第二次映射的处理 if(date[i + 1] > date[i] + 1){ if((date[i + 1] - 1) - (date[i] + 1) >= n) { // 压缩区间长度超过 n 时 b[++Cnt] = Seg[0].tree[1].min; continue; } int l = (date[i] + 1) % n, r = (date[i + 1] - 1) % n; //映射到复制前的序列中的位置 if(l == 0) l = n; if(r == 0) r = n; if(l <= r) b[++Cnt] = Seg[0].Get_min(1, 1, n, l, r); // 在一个区间内 else b[++Cnt] = min(Seg[0].Get_min(1, 1, n, 1, r), Seg[0].Get_min(1, 1, n, l, n)); // 不在一个区间内，用两段区间合并 } } if(date[date_num] % n == 0) b[++Cnt] = a[n]; else b[++Cnt] = a[date[date_num] % n]; pre[date_num] = Cnt; for(int i = 1; i <= m; ++i) { q[i].l = lower_bound(date + 1, date + date_num + 1, q[i].l) - date; // 询问的点向离散化后映射 q[i].r = lower_bound(date + 1, date + date_num + 1, q[i].r) - date; q[i].l = pre[q[i].l], q[i].r = pre[q[i].r]; // 向b序列中的映射 } Seg[1].Build(1, 1, Cnt); //对 b序列建树 for(int i = 1; i <= m; ++i) { //直接修改+查询即可 if(q[i].opt == 1) Seg[1].Change(1, 1, Cnt, q[i].l, q[i].r, q[i].val); else printf("%d\n", Seg[1].Get_min(1, 1, Cnt, q[i].l, q[i].r)); } return 0;}
        
       
      
     
    
   

总结

对于所维护的区间过大时，考虑离散化只留下有用的信息来达到节约空间的目的。

CF915E Physical Education Lessons

Description

题面：

一个长度为 \(1e9\) 的 \(01\) 序列，开始都是1，要求支持区间修改 \(0/1\) ,每次修改后都要输出整个序列中 \(1\) 的个数

Solution

\(1e9\) 开不下啊，考虑动态开点线段树

维护操作时和线段树类似，用到哪块区间就新建哪块区间（例如询问时和下放懒标记时）

Code

/*Work by: Suzt_ilymicsKnowledge: 动态开点线段树 Time: O(能过)当线段树维护的范围到达1e9*/#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define LL long long#define orz cout<<"lkp AK IOI!"<
        
         << 1) + (s << 3) + ch - '0' , ch = getchar(); return f ? -s : s;}namespace CMT{ int root, node_num = 0, sum[MAXN], lazy[MAXN], lson[MAXN], rson[MAXN]; void Push_up(int i) { sum[i] = sum[lson[i]] + sum[rson[i]]; } void Push_down(int i, int l, int r) { // 一次只需要开两个点，剩下的点用到的时候在开，节省空间 if(lazy[i] == -1) return ; int mid = (l + r) >> 1; // 确定序列的长度 if(!lson[i]) lson[i] = ++ node_num; // 没有的话就开一个点 if(!rson[i]) rson[i] = ++ node_num; sum[lson[i]] = lazy[i] * (mid - l + 1), lazy[lson[i]] = lazy[i]; sum[rson[i]] = lazy[i] * (r - mid), lazy[rson[i]] = lazy[i]; lazy[i] = -1; } void Change(int &now_, int l, int r, int L, int R, int val) { if(!now_) now_ = ++ node_num; // 如果没有这个结点，新建这个结点 if(L <= l && r <= R) { sum[now_] = (r - l + 1) * val; // lazy[now_] = val; return ; } Push_down(now_, l, r); // 如果需要更精确的序列，就下放新建结点 int mid = (l + r) >> 1; if(mid >= L) Change(lson[now_], l, mid, L, R, val); if(mid < R) Change(rson[now_], mid + 1, r, L, R, val); Push_up(now_); }}using namespace CMT;int main(){ n = read(), m = read(); memset(lazy, -1, sizeof lazy); Change(root, 1, n, 1, n, 0); // 用0表示有工作日，1表示非工作日 for(int i = 1, l, r, k; i <= m; ++i) { l = read(), r = read(), k = read(); Change(root, 1, n, l, r, 2 - k); printf("%d\n", n - sum[1]); } return 0;}
        
       
      
     
    
   

P6327 区间加区间sin和

Description

Solution

根据三角恒等变换公式，有

主要是要证明 \(\sin\) 能够满足区间加的性质

证明如下：

设有两个角 \(a, b\)，新加的值为 \(k\)， 则

将上面的公式代入化简即可，同时发现 \(\cos\) 也能化成类似的形式

那么一切就好做了，按照上面两个结论修改即可

Code

/*Work by: Suzt_ilymicsKnowledge: ??Time: O(??)*/#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define LL long long#define int long long#define orz cout<<"lkp AK IOI!"<
        
         << 1) + (s << 3) + ch - '0' , ch = getchar(); return f ? -s : s;}namespace Seg{ #define lson i << 1 #define rson i << 1 | 1 struct Tree{ double Sin, Cos; int lazy; }tree[MAXN << 2]; void Push_up(int i) { tree[i].Sin = tree[lson].Sin + tree[rson].Sin; tree[i].Cos = tree[lson].Cos + tree[rson].Cos; } void Build(int i, int l, int r) { if(l == r) { tree[i].Sin = sin(a[l]); tree[i].Cos = cos(a[l]); return ; } int mid = (l + r) >> 1; Build(lson, l, mid), Build(rson, mid + 1, r); Push_up(i); } void Push_down(int i) { if(tree[i].lazy) { tree[lson].lazy += tree[i].lazy; tree[rson].lazy += tree[i].lazy; double Sin_lson = tree[lson].Sin, Sin_rson = tree[rson].Sin; int tag = tree[i].lazy; tree[lson].Sin = Sin_lson * cos(tag) + tree[lson].Cos * sin(tag); tree[lson].Cos = tree[lson].Cos * cos(tag) - Sin_lson * sin(tag); tree[rson].Sin = Sin_rson * cos(tag) + tree[rson].Cos * sin(tag); tree[rson].Cos = tree[rson].Cos * cos(tag) - Sin_rson * sin(tag); tree[i].lazy = 0; } } void Add(int i, int l, int r, int L, int R, int val) { if(L <= l && r <= R) { double Sin = tree[i].Sin; tree[i].Sin = tree[i].Sin * cos(val) + tree[i].Cos * sin(val); tree[i].Cos = tree[i].Cos * cos(val) - Sin * sin(val); tree[i].lazy += val; return ; } Push_down(i); int mid = (l + r) >> 1; if(mid >= L) Add(lson, l, mid, L, R, val); if(mid < R) Add(rson, mid + 1, r, L, R, val); Push_up(i); } double Get_Sin(int i, int l, int r, int L, int R) { if(L <= l && r <= R) return tree[i].Sin; Push_down(i); int mid = (l + r) >> 1; double ans = 0; if(mid >= L) ans += Get_Sin(lson, l, mid, L, R); if(mid < R) ans += Get_Sin(rson, mid + 1, r, L, R); return ans; }}signed main(){ n = read(); for(int i = 1; i <= n; ++i) a[i] = read(); Seg::Build(1, 1, n); m = read(); for(int i = 1, opt, l, r, val; i <= m; ++i) { opt = read(), l = read(), r = read(); if(opt == 1) { val = read(); Seg::Add(1, 1, n, l, r, val); } else { double Ans = Seg::Get_Sin(1, 1, n, l, r); printf("%.1f\n", Ans); } } return 0;}
        
       
      
     
    
   

CF242E XOR on Segment

Description

Solution

手膜一下发现，当区间和加起来时不能直接进行区间异或，因为不能满足类似于上面那个题的性质

这里我们考虑使用拆位线段树

将每一个数进行二进制拆分，对每个二进制位分别建树

又因为 1^1=0, 0^1=1 和 1^0=1, 0^0=0

即，异或 \(1\) 时进行取反，否则不变

所以区间异或时取出每一位，是 \(1\) 就进行修改，否则无需修改，修改操作也十分类似于区间翻转

Code

/*Work by: Suzt_ilymicsKnowledge: ??Time: O(??)*/#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define LL long long#define int long long#define orz cout<<"lkp AK IOI!"<
        
         << 1) + (s << 3) + ch - '0' , ch = getchar(); return f ? -s : s;}struct SEG{ #define lson i << 1 #define rson i << 1 | 1 struct Tree{ int sum, lazy, len; }tree[MAXN << 2]; void Push_up(int i) { tree[i].sum = tree[lson].sum + tree[rson].sum; } void Build(int i, int l, int r, int rk) { tree[i].len = r - l + 1; if(l == r) { tree[i].sum = a[rk][l]; return ; } int mid = (l + r) >> 1; Build(lson, l, mid, rk), Build(rson, mid + 1, r, rk); Push_up(i); } void Push_down(int i) { if(tree[i].lazy) { tree[lson].lazy ^= 1, tree[rson].lazy ^= 1; tree[lson].sum = tree[lson].len - tree[lson].sum; tree[rson].sum = tree[rson].len - tree[rson].sum; tree[i].lazy = 0; } } void Xor(int i, int l, int r, int L, int R, int val) { if(L <= l && r <= R) { tree[i].sum = tree[i].len - tree[i].sum; tree[i].lazy ^= val; return ; } Push_down(i); int mid = (l + r) >> 1; if(mid >= L) Xor(lson, l, mid, L, R, val); if(mid < R) Xor(rson, mid + 1, r, L, R, val); Push_up(i); } int Get_sum(int i, int l, int r, int L, int R) { if(L <= l && r <= R) return tree[i].sum; Push_down(i); int mid = (l + r) >> 1, ans = 0; if(mid >= L) ans += Get_sum(lson, l, mid, L, R); if(mid < R) ans += Get_sum(rson, mid + 1, r, L, R); return ans; }}Seg[21];signed main(){ n = read(); for(int i = 1, x; i <= n; ++i) { x = read(); for(int j = 0; j <= 20; ++j) a[j][i] = ((x >> j) & 1); } for(int i = 0; i <= 20; ++i) Seg[i].Build(1, 1, n, i); m = read(); for(int i = 1, opt, l, r, x; i <= m; ++i) { opt = read(), l = read(), r = read(); if(opt == 1) { ans = 0; for(int j = 0; j <= 20; ++j) ans += (1 << j) * Seg[j].Get_sum(1, 1, n, l, r); printf("%lld\n", ans); } else { x = read(); for(int j = 0; j <= 20; ++j) { if((x >> j) & 1) Seg[j].Xor(1, 1, n, l, r, 1); } } } return 0;}
        
       
      
     
    
   

CF438D The Child and Sequence

Description

Solution

特点在于区间取模

其实和 花神游历各国 和 GSS4 的思路类似

可以证明：如果模数 \(m \le x\)，则 \(x \mod m < \frac{x}{2}\)

那么最多只会模 \(\log x\) 次，和区间开方一样的处理方式即可（维护一个区间最值，暴力开方）

证明：

• 如果 \(m > x\), 那么 \(x \mod m = x\)

• 如果 \(m < x\)，考虑如何让 \(x\) 剩下的值最大？一个显然的想法是模数 \(m\) 尽可能大

  如果 \(m > \frac{x}{2}\) ，那么剩下的一定小于 \(\frac{x}{2}\)，如果 \(m < \frac{x}{2}\)，那么更不必说了，所以当 \(m = \frac{x}{2}\) 时，\(x\) 剩下的值最大，所以 \(x\) 最多进行取模 \(\log x\) 次

代码的话，应该和区间开方差不多吧

Code

/*Work by: Suzt_ilymicsKnowledge: ??Time: O(??)*/#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define LL long long#define int long long#define orz cout<<"lkp AK IOI!"<
        
         << 1) + (s << 3) + ch - '0' , ch = getchar(); return f ? -s : s;}namespace Seg{ #define lson i << 1 #define rson i << 1 | 1 struct Tree{ int sum, max; }tree[MAXN << 2]; void Push_up(int i) { tree[i].sum = tree[lson].sum + tree[rson].sum; tree[i].max = max(tree[lson].max, tree[rson].max); } void Build(int i, int l, int r) { if(l == r) { tree[i].max = tree[i].sum = a[l]; return ; } int mid = (l + r) >> 1; Build(lson, l, mid), Build(rson, mid + 1, r); Push_up(i); } void Change(int i, int l, int r, int L, int R, int k) { if(L <= l && r <= R) { tree[i].max = tree[i].sum = k; return ; } int mid = (l + r) >> 1; if(mid >= L) Change(lson, l, mid, L, R, k); else Change(rson, mid + 1, r, L, R, k); Push_up(i); } void Sec_Mod(int i, int l, int r, int L, int R, int k) { if(tree[i].max < k) return ; if(l == r) { tree[i].sum = tree[i].max = tree[i].sum % k; return ; } int mid = (l + r) >> 1; if(mid >= L) Sec_Mod(lson, l, mid, L, R, k); if(mid < R) Sec_Mod(rson, mid + 1, r, L, R, k); Push_up(i); } int Get_Sum(int i, int l, int r, int L, int R) { if(L <= l && r <= R) return tree[i].sum; int mid = (l + r) >> 1, ans = 0; if(mid >= L) ans += Get_Sum(lson, l, mid, L, R); if(mid < R) ans += Get_Sum(rson, mid + 1, r, L, R); return ans; }}signed main(){ n = read(), m = read(); for(int i = 1; i <= n; ++i) a[i] = read(); Seg::Build(1, 1, n); for(int i = 1, opt, l, r, k; i <= m; ++i) { opt = read(), l = read(), r = read(); if(opt == 1) printf("%lld\n", Seg::Get_Sum(1, 1, n, l, r)); else if(opt == 2) k = read(), Seg::Sec_Mod(1, 1, n, l, r, k); else Seg::Change(1, 1, n, l, l, r); } return 0;}
        
       
      
     
    
   

CF703D Mishka and Interesting sum

Description

Solution

• 树状数组

Code

/*Work by: Suzt_ilymicsKnowledge: 树状数组 Time: O(能过)*/#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define LL long long#define orz cout<<"lkp AK IOI!"<
        
         << 1) + (s << 3) + ch - '0' , ch = getchar(); return f ? -s : s;}int lowbit(int x) { return x & (-x); }void Add(int x, int val) { for(int i = x; i <= n; i += lowbit(i)) tree[i] ^= val; }int Query(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res ^= tree[i]; return res;}int main(){ n = read(); for(int i = 1; i <= n; ++i) a[i] = date[i] = read(); sort(date + 1, date + n + 1), date[0] = -INF; for(int i = 1; i <= n; ++i) if(date[i] != date[i - 1]) date[++ date_num] = date[i]; for(int i = 1; i <= n; ++i) a[i] = lower_bound(date + 1, date + date_num + 1, a[i]) - date; for(int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] ^ date[a[i]]; pre[i] = head[a[i]], head[a[i]] = i; } m = read(); for(int i = 1; i <= m; ++i) q[i].Read(i); sort(q + 1, q + m + 1); for(int i = 1; i <= m; ++i) { while(now_ <= q[i].r) { if(pre[now_]) Add(pre[now_], date[a[now_]]); Add(now_, date[a[now_]]); ++ now_; } ans[q[i].bh] = (Query(q[i].r) ^ Query(q[i].l - 1)) ^ sum[q[i].r] ^ sum[q[i].l - 1]; } for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]); return 0;}
        
       
      
     
    
   

P4211 [LNOI2014]LCA

Solution:

嗯……主要在题目转化方面

\(dep[LCA(i,z)]\) 就是 \(i\) 和 \(z\) 到根节点的路径重合的部分。

那么计算 \(i\) 的贡献时可以先用线段树把 \(1 \to i\) 这一段加 \(1\)，然后查询 \(1 \to x\) 这一段区间的值。每次做的复杂度为 \(O(n \log n \log n)\)还要做 \(q\) 次

一个很神奇的思路，差分！

考虑离线处理。区间 \([l,r]\) 可以拆解成 \([1,r] - [1,l-1]\)。把这些左右端点标记下来（这里用的vector储存的）所以可以从 \(1\) 加到 \(n\)，当遇到一个标记的端点，就立即计算它的贡献。

误区：一开始相成了树上差分，结果把整个题解区翻了一遍都没看懂做法

/*Work by: Suzt_ilymicsProblem: 不知名屑题Knowledge: 垃圾算法Time: O(能过)*/#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long#define orz cout<<"lkp AK IOI!"<
         
           a[MAXN];int read(){ int s = 0, f = 0; char ch = getchar(); while(!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar(); return f ? -s : s;}namespace Seg { #define lson i << 1 #define rson i << 1 | 1 struct Tree{ int len, lazy, sum; }tree[MAXN << 2]; void Push_up(int i) { tree[i].sum = tree[lson].sum + tree[rson].sum; } void Build(int i, int l, int r) { tree[i].len = r - l + 1; if(l == r) return ; int mid = (l + r) >> 1; Build(lson, l, mid), Build(rson, mid + 1, r); Push_up(i); } void Push_down(int i) { if(tree[i].lazy) { tree[lson].lazy += tree[i].lazy; tree[rson].lazy += tree[i].lazy; tree[lson].sum += tree[lson].len * tree[i].lazy; tree[rson].sum += tree[rson].len * tree[i].lazy; tree[i].lazy = 0; } } void Add(int i, int l, int r, int L, int R, int val) { if(L <= l && r <= R) { tree[i].sum += tree[i].len * val; tree[i].lazy += val; return ; } Push_down(i); int mid = (l + r) >> 1; if(mid >= L) Add(lson, l, mid, L, R, val); if(mid < R) Add(rson, mid + 1, r, L, R, val); Push_up(i); } int Query(int i, int l, int r, int L, int R) {// cout<
          
           <<" "<
           
            <<" "<
            
             <<" "<
             
              <<"\n"; if(L <= l && r <= R) return tree[i].sum; Push_down(i); int mid = (l + r) >> 1, ans = 0; if(mid >= L) ans += Query(lson, l, mid, L, R); if(mid < R) ans += Query(rson, mid + 1, r, L, R); return ans; } }namespace Cut { struct edge { int to, nxt; }e[MAXN << 1]; int head[MAXN], num_edge = 1; void add_edge(int from, int to) { e[++num_edge] = (edge){to, head[from]}, head[from] = num_edge; } void dfs(int u, int fa) {// cout<<"dfs1: "<
              <
               
                 siz[son[u]]) son[u] = v; } } void dfs2(int u, int tp) {// cout<<"dfs2: "<
                <
                 
                   dep[y]) swap(x, y); Seg::Add(1, 1, n, dfn[x], dfn[y], 1); } int Query(int x, int y) { int ans = 0; while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); ans += Seg::Query(1, 1, n, dfn[top[x]], dfn[x]); x = fath[top[x]]; } if(dep[x] > dep[y]) swap(x, y); ans += Seg::Query(1, 1, n, dfn[x], dfn[y]); return ans; }}int main(){// freopen("P4211_1.in","r",stdin);// freopen("P4211_1.out","w",stdout); n = read(), m = read(); for(int i = 2, x; i <= n; ++i) x = read() + 1, Cut::add_edge(i, x), Cut::add_edge(x, i); Cut::dfs(1, 0), Cut::dfs2(1, 1), Seg::Build(1, 1, n); for(int i = 1, l, r, z; i <= m; ++i) { l = read() + 1, r = read() + 1, z = read() + 1; a[l - 1].push_back((node){i, z, 0}); a[r].push_back((node){i, z, 1}); } for(int i = 1; i <= n; ++i) { Cut::Add(1, i); for(int j = 0; j < a[i].size(); ++j) { if(a[i][j].type) {// cout<<"type1: "<
                  
                   <<"\n"; ans[a[i][j].pre] = (ans[a[i][j].pre] + Cut::Query(1, a[i][j].z)) % mod; } else {// cout<<"type0: "<
                   
                    <<"\n"; ans[a[i][j].pre] = (ans[a[i][j].pre] - Cut::Query(1, a[i][j].z) + mod) % mod; } } } for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]); return 0;}