南宁门户网站有哪些,海珠建网站公司,wordpress标题间隔符修改,郑州文明网正题
解题思路:https://www.luogu.org/recordnew/lists?uid52918pidP3870 题目大意
n个灯#xff0c;操作[0,l,r][0,l,r][0,l,r]表示l∼rl\sim rl∼r的灯取反#xff0c;操作[1,l,r][1,l,r][1,l,r]表示询问l∼rl\sim rl∼r之间有多少灯亮着。 解题思路
分块#xf…正题
解题思路:https://www.luogu.org/recordnew/lists?uid52918pidP3870 题目大意
n个灯操作[0,l,r][0,l,r][0,l,r]表示l∼rl\sim rl∼r的灯取反操作[1,l,r][1,l,r][1,l,r]表示询问l∼rl\sim rl∼r之间有多少灯亮着。 解题思路
分块对于每个块维护两个值sum,fsum,fsum,f。sum表示这个块有多少个开着的灯f表示这个块是否取反。 由于有了f所以我们对于块就可以不用取反了。 code
#includecstdio
#includecmath
#define pos(x) (x-1)/sq1
#define N 100010
#define T 500
using namespace std;
int n,m,l,r,x,sq,t;
bool a[N],f[T];
int L[T],R[T],sum[T];
void ycl()
{sqtsqrt(n);for(int i1;it;i){L[i](i-1)*t1;R[i]i*t;}if(R[t]n) t,L[t]R[t-1]1,R[t]n;
}
void change(int l,int r)
{int qpos(l),ppos(r);if(qp){for(int il;ir;i)sum[p]1-a[i]*2,a[i]!a[i];}else{for(int iq1;ip-1;i)f[i]!f[i];for(int il;iR[q];i)sum[q]1-a[i]*2,a[i]!a[i];for(int iL[p];ir;i)sum[p]1-a[i]*2,a[i]!a[i];}
}
int ask(int l,int r)
{int ans0;int qpos(l),ppos(r);if(qp){for(int il;ir;i)ansa[i];if(f[p]) return r-l1-ans;return ans;}else{for(int iq1;ip-1;i)if(f[i]) ansR[i]-L[i]1-sum[i];else anssum[i];int k0;for(int il;iR[q];i)ka[i];if(f[q]) ansR[q]-l1-k;else ansk;k0;for(int iL[p];ir;i)ka[i];if(f[p]) ansr-L[p]1-k;else ansk;}return ans;
}
int main()
{scanf(%d%d,n,m);ycl();for(int i1;im;i){scanf(%d%d%d,x,l,r);if(x) printf(%d\n,ask(l,r));else change(l,r);}
}
