题解：CF1172F Nauuo and Bug
zhangjiting
·
·
题解
思路
扫描线，扫到一个左端点就向平衡树插入一个 0，记录下这个节点的编号。
每扫过一个 i 就按 p-a_i-1 分成两棵子树 x,y。
把 $x,y$ 合并起来，值域有交，采用一段一段合并的方式。
扫到右端点，取出对应编号的值，注意要加上根节点到这个节点的懒标记。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cerr<<#x<<':'<<x<<endl
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
int n,m,mod;
int a[N];
int id[N];
int val[N],tag[N],fa[N],lc[N],rc[N],key[N];
int tot,root;
int ans[N];
vector<int> L[N],R[N];
mt19937 rnd(time(0));
inline int new_node(int x){
tot++;
val[tot]=x,key[tot]=rnd();
return tot;
}
inline void push_up(int p){
fa[p]=0;
if(lc[p]) fa[lc[p]]=p;
if(rc[p]) fa[rc[p]]=p;
}
inline void push_down(int p){
if(!tag[p]) return;
if(lc[p]) val[lc[p]]+=tag[p],tag[lc[p]]+=tag[p];
if(rc[p]) val[rc[p]]+=tag[p],tag[rc[p]]+=tag[p];
tag[p]=0;
}
void split(int p,int k,int &x,int &y){
if(!p) return x=y=0,void();
push_down(p);
if(val[p]<=k){
x=p;
split(rc[p],k,rc[x],y);
push_up(x);
}
else{
y=p;
split(lc[p],k,x,lc[y]);
push_up(y);
}
}
int merge(int x,int y){
if(!x||!y) return x|y;
push_down(x),push_down(y);
if(key[x]>key[y]){
rc[x]=merge(rc[x],y);
push_up(x);
return x;
}
else{
lc[y]=merge(x,lc[y]);
push_up(y);
return y;
}
}
inline int ins(int x){
int a,b;
split(root,x,a,b);
int p=new_node(x);
root=merge(a,merge(p,b));
return p;
}
int mi(int x){
while(lc[x]) push_down(x),x=lc[x];
return val[x];
}
inline void change(int x){
int a,b;
split(root,mod-x-1,a,b);
if(a) val[a]+=x,tag[a]+=x;
if(b) val[b]+=x-mod,tag[b]+=x-mod;
root=0;
if(mi(a)>mi(b)) swap(a,b);
while(b){
int u,v;
split(a,mi(b),u,v);
root=merge(root,u);
a=v,swap(a,b);
}
root=merge(root,a);
}
inline int query(int x){
int res=val[x];
while(fa[x]) x=fa[x],res+=tag[x];
return res;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
IOS;
cin>>n>>m>>mod;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1,l,r;i<=m;i++){
cin>>l>>r;
L[l].push_back(i),R[r].push_back(i);
}
for(int i=1;i<=n;i++){
for(int x:L[i]) id[x]=ins(0);
change(a[i]);
for(int x:R[i]) ans[x]=query(id[x]);
}
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}
```