珠海市网站建设,全球十大跨境电商平台,网站建设外包公司招聘,wordpress主题 破解主题下载地址题目链接
点击打开链接
题目解法
转化很妙
考虑关路灯 x x x 的操作 令左边第一个未关的路灯为 L L L#xff0c;右边第一个未关的路灯为 R R R#xff0c;那么这一次会影响的区间即为 l ∈ [ L 1 , x ] , r ∈ [ x , R − 1 ] l\in[L1,x],\;r\in[x,R-1] l∈[L1,x],…题目链接
点击打开链接
题目解法
转化很妙
考虑关路灯 x x x 的操作 令左边第一个未关的路灯为 L L L右边第一个未关的路灯为 R R R那么这一次会影响的区间即为 l ∈ [ L 1 , x ] , r ∈ [ x , R − 1 ] l\in[L1,x],\;r\in[x,R-1] l∈[L1,x],r∈[x,R−1]既然有 2 个限制那么我们把限制变成二维平面上的矩阵即把左上为 ( L 1 , x ) (L1,x) (L1,x)右下为 ( x , R − 1 ) (x,R-1) (x,R−1) 的矩阵变为 0 开路灯的操作类似
考虑询问的是什么 即 1 1 1 到 q − 1 q-1 q−1 次每个版本 ( x , y ) (x,y) (x,y) 位置的和 考虑给矩阵定义一个增加或减少值使查询变成只要查询第 i i i 个版本的 ( x , y ) (x,y) (x,y) 值 这里直接给出对于第 i i i 个操作加上或减去值为 i − q i-q i−q 考虑先开路灯再关路灯的操作即为 T − i − ( T − j ) j − i T-i-(T-j)j-i T−i−(T−j)j−i恰好为答案这可以拓展到多个开关路灯的操作 这里需要一个特判如果查询第 i i i 个版本从 x x x 可以到 y y y那么答案需要 − ( q − i ) -(q-i) −(q−i)
可以把矩形变成 4 个区域的加减然后不难发现这就是一个三维偏序可以考虑离线 c d q cdq cdq 时间复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)
#include bits/stdc.h
#define lowbit(x) x-x
using namespace std;
const int N300100;
struct Node{ int x1,x2,v,op,id;}q[N*10],t[N*10];
int idx,n,m,state[N],ans[N],tr[N];
char str[N];
setint se;
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void ADD(int x,int y,int v){ q[idx]{x,y,v,0,0};}
void add_square(int x1,int x2,int y1,int y2,int v){ADD(x2,y2,v);if(x11) ADD(x1-1,y2,-v);if(y11) ADD(x2,y1-1,-v);if(x11y11) ADD(x1-1,y1-1,v);
}
void work(int x,int t){if(!state[x]){auto itse.upper_bound(x);int R*it,L*(--it);se.insert(x);add_square(L1,x,x,R-1,-(m-t));}else{se.erase(x);auto itse.upper_bound(x);int R*it,L*(--it);add_square(L1,x,x,R-1,m-t);}
}
void add(int x,int y){ for(;xn;xlowbit(x)) tr[x]y;}
int ask(int x){if(!x) return 0;int res0;for(;x;x-lowbit(x)) restr[x];return res;
}
void cdq(int l,int r){if(lr) return;int mid(lr)1;cdq(l,mid),cdq(mid1,r);int il,jmid1,k0;while(imid||jr){if(jr||(imidq[i].x1q[j].x1)){if(!q[i].op) add(q[i].x2,q[i].v);t[k]q[i],i;}else{if(q[j].op) ans[q[j].id]ask(n)-ask(q[j].x2-1);t[k]q[j],j;}}for(il;imid;i) if(!q[i].op) add(q[i].x2,-q[i].v);for(int i1,jl;ik;i,j) q[j]t[i];
}
bool con(int x,int y){ return ask(y)-ask(x-1)y-x1;}
int main(){nread(),mread();scanf(%s,str1);for(int i1;in;i) state[i]str[i]-48;add_square(1,n,1,n,m);se.insert(0),se.insert(n1);for(int i1;in;i) if(state[i]) add(i,1);for(int i1;in;i) if(!state[i]) work(i,0);for(int i1;im;i){char op[10];scanf(%s,op);if(op[0]t){int xread();state[x]^1,work(x,i);ans[i]-1e9;if(state[x]) add(x,1);else add(x,-1);}else{int xread(),yread();y--;if(con(x,y)) ans[i]-(m-i);q[idx]{x,y,0,1,i};}}memset(tr,0,sizeof(tr));cdq(1,idx);for(int i1;im;i) if(ans[i]!-1e9) printf(%d\n,ans[i]);return 0;
}
