[APIO2019] [LOJ 3146] 路灯 (cdq分治或树状数组套线段树)
题面
略
分析
首先把一组询问(x,y)看成二维平面上的一个点，我们想办法用数据结构维护这个二维平面(注意根据题意这里的y要-1，这样问题变成[x,y]区间是否是由连续的一段1组成)
如果我们改变第x个灯的状态,那么只有原来满足全1的条件，且现在不满足全1条件的区间受到影响。设包含x的最大的连续1的区间为[l,r],则左端点在[l,x]，右端点在[x,r]的询问会受到影响。转化到二维平面上，就变成x坐标在[l,x]之内，y坐标在[x,r]之间的点会受到影响。即左下角为(l,x),右上角为(x,r)的矩形内的点
然后考虑每次修改对答案的影响。假如一个灯在t1时刻被点亮，t2时刻被熄灭，则它对答案的贡献为\(t_2-t_1\)。因此，如果时间为i时的修改使得第x个灯被点亮，我们就把左下角为(l,x),右上角为(x,r)的矩形内的点的值-i。如果时间为i时的修改使得第x个灯被熄灭，我们就把左下角为(l,x),右上角为(x,r)的矩形内的点的值+i
对于时间为i的询问(x,y),我们查询点(x,y)的值v，如果当前不能从x到y，那就直接输出v.否则,就输出i+v.因为只有某个灯熄灭的时候我们才更新它的贡献，如果询问时没熄灭，就要加上这些贡献。
这样，我们就把问题转化成二维的区间修改，单点查询问题，可以用标记永久化的二维线段树解决，但是代码实现难度较大。我们可以差分，把问题转化为二维的单点修改，区间查询问题
如果把左下角为 \((x_a,y_a)\)，右上角\((x_b,y_b)\)的闭区间都加一个 v，那么其实就是:\((x_a,y_a)\)\(加v,\)
\((x_a,y_b+1)\)减 v,\((x_b+1,y_a)\)减 v,\((x_b+1,y_b+1)\)加 v.查询\((x,y)\)就查询(1,1)到\((x,y)\)的矩形内的点的权值和
这是一个经典的cdq分治问题，方法类似：[BZOJ 2683] 简单题 (CDQ分治)
也可以用树状数组维护第一维，动态开点的线段树维护第二维在线求解
时间复杂度均为\(O(n\log^2 n)\)
找全1的区间用set维护0的位置，二分查找出左边的第一个0和右边的第一个0的位置即可
代码
cdq分治:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define maxn 300000
using namespace std;
typedef long long ll;
int n,m;
int a[maxn+5];
set<int>S;//存储0的位置
int tot;
struct node{
int a;
int b;
int c;
int type;
int val;
int id;
ll ans;
node(){
}
node(int _a,int _b,int _c,int _type,int _val){
a=_a;
b=_b;
c=_c;
type=_type;
val=id=ans=0;
if(_type==2) id=_val;
else val=_val;
}
void print(){
if(type==1){
printf("update tim=%d (%d,%d) val=%d\n",a,b,c,val);
}else{
printf("query tim=%d (%d,%d) id=%d\n",a,b,c,id);
}
}
}q[maxn*4+5];
int cmpa(node p,node q){
if(p.a==q.a){
if(p.b==q.b) return p.c<q.c;
else return p.b<q.b;
}else return p.a<q.a;
}
int cmpb(node p,node q){
if(p.b==q.b) return p.c<q.c;
else return p.b<q.b;
}
struct fenwick_tree{
ll c[maxn+5];
inline int lowbit(int x){
return x&(-x);
}
inline void update(int pos,int val){
for(int i=pos;i<=maxn;i+=lowbit(i)) c[i]+=val;
}
inline ll query(int pos){
int ans=0;
for(int i=pos;i>0;i-=lowbit(i)) ans+=c[i];
return ans;
}
}T;
node tmp[maxn*4+5];
void cdq_divide(ll l,ll r){
int mid=(l+r)>>1;
if(l==r) return;
cdq_divide(l,mid);
cdq_divide(mid+1,r);
int ptr=l-1;
for(int i=mid+1;i<=r;i++){
while(ptr<mid&&q[ptr+1].b<=q[i].b){
ptr++;
if(q[ptr].type==1) T.update(q[ptr].c,q[ptr].val);
}
if(q[i].type==2) q[i].ans+=T.query(q[i].c);
}
for(int i=l;i<=ptr;i++) if(q[i].type==1) T.update(q[i].c,-q[i].val);
int pl=l,pr=mid+1;
int num=l-1;
while(pl<=mid&&pr<=r){
if(cmpb(q[pl],q[pr])) tmp[++num]=q[pl++];
else tmp[++num]=q[pr++];
}
while(pl<=mid) tmp[++num]=q[pl++];
while(pr<=r) tmp[++num]=q[pr++];
for(int i=l;i<=r;i++) q[i]=tmp[i];
}
ll ans[maxn+5];
int main(){
char cmd[10];
int l,r;
int x;
int cntq=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%1d",&a[i]);
for(int i=1;i<=n;i++){
if(a[i]==0) S.insert(i);
}
S.insert(0);
S.insert(n+1);
for(int i=1;i<=m;i++){
scanf("%s",cmd);
if(cmd[0]=='q'){
cntq++;
scanf("%d %d",&l,&r);
r--;
q[++tot]=node(i,l,r,2,cntq);
set<int>::iterator it1=S.upper_bound(l);
if(*it1>r&&a[l]==1&&a[r]==1){
ans[cntq]+=i;
// printf("(%d,%d) + %d\n",l,r,i);
}
}else{
scanf("%d",&x);
a[x]^=1;
if(a[x]==1){//亮起
set<int>::iterator pre=S.lower_bound(x);
pre--;
set<int>::iterator nex=S.upper_bound(x);
l=*pre+1;
r=*nex-1;
// printf("for x in [%d,%d], y in [%d,%d],+%d\n",l,x,x,r,-i);
q[++tot]=node(i,l,x,1,-i);
q[++tot]=node(i,l,r+1,1,i);
q[++tot]=node(i,x+1,x,1,i);
q[++tot]=node(i,x+1,r+1,1,-i);
S.erase(x);
}else{//熄灭
set<int>::iterator pre=S.lower_bound(x);
pre--;
set<int>::iterator nex=S.upper_bound(x);
l=*pre+1;
r=*nex-1;
// printf("for x in [%d,%d], y in [%d,%d],+%d\n",l,x,x,r,i);
q[++tot]=node(i,l,x,1,i);
q[++tot]=node(i,l,r+1,1,-i);
q[++tot]=node(i,x+1,x,1,-i);
q[++tot]=node(i,x+1,r+1,1,i);
S.insert(x);
}
}
}
// for(int i=1;i<=tot;i++) q[i].print();
sort(q+1,q+1+tot,cmpa);
cdq_divide(1,tot);
for(int i=1;i<=tot;i++){
if(q[i].type==2) ans[q[i].id]+=q[i].ans;
}
for(int i=1;i<=cntq;i++) printf("%lld\n",ans[i]);
}
树套树:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define maxn 300000
#define maxlogn 50
using namespace std;
typedef long long ll;
int n,m;
int a[maxn+5];
set<int>S;//存储0的位置
struct dynamic_segment_tree{
#define lson(x) tree[x].ls
#define rson(x) tree[x].rs
struct node{
int ls;
int rs;
ll val;
}tree[maxn*maxlogn+5];
int ptr=0;
void push_up(int x){
tree[x].val=tree[lson(x)].val+tree[rson(x)].val;
}
void update(int &x,int upos,ll uval,int l,int r){
if(!x) x=++ptr;
if(l==r){
tree[x].val+=uval;
return;
}
int mid=(l+r)>>1;
if(upos<=mid) update(tree[x].ls,upos,uval,l,mid);
else update(tree[x].rs,upos,uval,mid+1,r);
push_up(x);
}
ll query(int x,int L,int R,int l,int r){
if(x==0) return 0;
if(L<=l&&R>=r) return tree[x].val;
int mid=(l+r)>>1;
ll ans=0;
if(L<=mid) ans+=query(tree[x].ls,L,R,l,mid);
if(R>mid) ans+=query(tree[x].rs,L,R,mid+1,r);
return ans;
}
}T1;
struct fenwick_tree{
int root[maxn+5];
inline int lowbit(int x){
return x&(-x);
}
inline void update(int x,int y,ll val){
// printf("(%d,%d) + %d\n",x,y,val);
for(int i=x;i<=n+1;i+=lowbit(i)){
T1.update(root[i],y,val,1,n+1);
}
}
inline ll query(int x,int y){
ll ans=0;
for(int i=x;i>0;i-=lowbit(i)){
ans+=T1.query(root[i],1,y,1,n+1);
}
return ans;
}
}T2;
ll ans[maxn+5];
int main(){
char cmd[10];
int l,r;
int x;
int cntq=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%1d",&a[i]);
for(int i=1;i<=n;i++){
if(a[i]==0) S.insert(i);
}
S.insert(0);
S.insert(n+1);
for(int i=1;i<=m;i++){
scanf("%s",cmd);
if(cmd[0]=='q'){
cntq++;
scanf("%d %d",&l,&r);
r--;
set<int>::iterator it1=S.upper_bound(l);
if(*it1>r&&a[l]==1&&a[r]==1){
printf("%lld\n",T2.query(l,r)+i);
}else{
printf("%lld\n",T2.query(l,r));
}
}else{
scanf("%d",&x);
a[x]^=1;
if(a[x]==1){//亮起
set<int>::iterator pre=S.lower_bound(x);
pre--;
set<int>::iterator nex=S.upper_bound(x);
l=*pre+1;
r=*nex-1;
// printf("for x in [%d,%d], y in [%d,%d],+%d\n",l,x,x,r,-i);
T2.update(l,x,-i);
T2.update(l,r+1,i);
T2.update(x+1,x,i);
T2.update(x+1,r+1,-i);
S.erase(x);
}else{//熄灭
set<int>::iterator pre=S.lower_bound(x);
pre--;
set<int>::iterator nex=S.upper_bound(x);
l=*pre+1;
r=*nex-1;
T2.update(l,x,i);
T2.update(l,r+1,-i);
T2.update(x+1,x,-i);
T2.update(x+1,r+1,i);
// printf("for x in [%d,%d], y in [%d,%d],+%d\n",l,x,x,r,i);
S.insert(x);
}
}
}
}
/*
5 2
11011
toggle 3
query 3 4
*/