#C241024C. 传感器
标签（Label）
- 线段树
前言（Front talk）
$\qquad$猜猜问什么改了几个小时才改出来 ？详见 AFO 小技巧 ，找到其中的序号 ⑤ 就指的这道题。
网址（Website）
题解（Solution）
$\qquad$这道题肯定是不能枚举每一次修改后的每一个传感器的状态，考虑一次修改对答案的影响。
$\qquad$一个传感器的影响区间可以被线段树分成 $\log n$ 个，如果每次修改都去判断传感器有没有被激活，最后还是会炸掉，发现只有传感器区间里面的红球只剩 $1$ 个或 $0$ 个的时候该传感器的激活状态才会变化，我们可以只在每个区间的红球和变成 $1$ 或 $0$ 的时候再处理区间问题。
$\qquad$记录一个区间的红球数量（最开始就是 siz = r-l+1 ），每次修改时，如果当前访问到的线段树节点的红球总和变成了 $0$ 或 $1$ ，才把对应区间的红球数量更新，并且更新区间内的红球数量，这道题就做好了。
$\qquad$时间复杂度 $O(n\log n)$ 。
$\qquad$可以使用 #define int long long ，常数优秀比谁都快。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define ull long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 501234;
bool ST;
int T,tid,Tim;
int n,m,a[N];ull ans;
int cnt[N];
P b[N];
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
struct Tr{int sum;vector<int> g;}tr[N<<2|3];
void build(int p,int l,int r){
tr[p].g.clear();
if(l==r) return tr[p].sum = 1, void();
build(ls,l,mid), build(rs,mid+1,r);
tr[p].sum=tr[ls].sum+tr[rs].sum;
}
void insert(int p,int l,int r,int L,int R,int id){
if(L<=l && r<=R) return tr[p].g.emplace_back(id),void();
if(L<=mid) insert(ls,l,mid,L,R,id);
if(R>mid) insert(rs,mid+1,r,L,R,id);
}
void update(int p,int l,int r,int pos){
if(l==r){
for(auto x:tr[p].g){
cnt[x]-=1;
int u=cnt[x];
if(u==1) ans+=1ll*x*x;
if(u==0) ans-=1ll*x*x;
}return tr[p].sum=0, void();
}
if(pos<=mid) update(ls,l,mid,pos);
else update(rs,mid+1,r,pos);
tr[p].sum=tr[ls].sum+tr[rs].sum;
if(tr[p].sum==1) for(auto x:tr[p].g){
cnt[x]-=r-l;
int u=cnt[x];
if(u==1) ans+=1ll*x*x;
if(u==0) ans-=1ll*x*x;
}else if(tr[p].sum==0) for(auto x:tr[p].g){
cnt[x]--;
int u=cnt[x];
if(u==1) ans+=1ll*x*x;
if(u==0) ans-=1ll*x*x;
}
}
void write(long long x){
if(x/10) write(x/10);
putchar(x%10^48);
}
void Solve(){
ans=0;
n = rd(), m = rd(), build(1,0,n-1);
For(i,1,m){
b[i] = {rd(), rd()}, cnt[i] = b[i].y-b[i].x+1;
insert(1,0,n-1,b[i].x,b[i].y,i);
if(cnt[i]==1) ans+=1ll*i*i;
}
write(ans),putchar(' ');
For(i,1,n){
a[i] = rd();
if(tid) a[i] = (a[i]+ans)%n;
update(1,0,n-1,a[i]);
write(ans),putchar(' ');
}puts("");
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("sensor.in","r",stdin);
freopen("sensor.out","w",stdout);
T = rd(), tid = rd();Tim = clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
