YZOJ P4444 [APIO2019]路灯
时间限制:5000MS 内存限制:524288KB
难度:\(7.0\)
-
题目描述
一辆自动驾驶的士正在 \(Innopolis\) 的街道上行驶。该街道上有 \(n+1\) 个停车站点,它们将街道划分成了 \(n\) 条路段。每一路段都拥有一个路灯。当第 \(i\) 个路灯亮起,它将照亮连接第 \(i\) 与第 \(i+1\)个站点的路段。否则这条路段将是黑暗的。
出于安全性的考虑,自动驾驶的士只能行驶在被照亮的路段上。换言之,的士能从站点 \(a\) 出发到达站点 \(b\) \((a<b)\) 的条件是:连接站点 \(a\) 与 \(a+1\),\(a+1\) 与 \(a+2, \cdots ,b-1\) 与 \(b\) 的路段都被照亮。
在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。
现在给定 \(0\) 时刻时,街道上路灯的初始状态。之后 \(1,2,\cdots,q\) 时刻,每时刻会发生下列两种事件之一:
\(toggle i\):切换第 \(i\) 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。
\(query a b\):自动驾驶的士部门的负责人想知道,从 \(0\) 时刻起到当前时刻,有多少个时刻满足:自动驾驶的士能够从站点 \(a\) 出发到达站点 \(b\) 。
请你帮助自动驾驶的士部门的负责人回答他们的问题。
-
输入格式
第一行包含两个整数 \(n\) 和 \(q\) \((1 \leq n,q \leq 300000)\) —- 表示路灯的数量与时刻数。
第二行包含一个字符串 \(s\) 表示路灯的初始状态 \((\left|s\right| = n)\), \(s_i\) 为 \(1\) 表示第 \(i\) 个路灯初始时亮起; \(s_i\) 为 \(0\) 表示第 \(i\) 个路灯初始时熄灭。
接下来 \(q\) 行每行描述一个时刻的事件。第 \(i\) 行描述时刻 \(i\) 所发生的事件。
\(toggle i\) \((1 \leq i \leq n)\):该时刻切换了第 \(i\) 个路灯的状态。
\(query a b\) \((1 \leq a < b \leq n+1)\):计算从 \(0\) 时刻起到该时刻,共有多少个时刻满足的士能从站点 \(a\) 出发到达站点 \(b\) 。
至少有一个时刻的事件是 \(query\) 。
-
输出格式
对于每个 \(query\) 的事件,输出一行单个整数,表示该问题的答案。
-
样例输入
1 2 3 4 5 6 7 8 9 |
5 7 11011 query 1 2 query 1 2 query 1 6 query 3 4 toggle 3 query 3 4 query 1 6 |
-
样例输出
1 2 3 4 5 6 |
1 2 0 0 1 2 |
// 原 2019.07.13
本题有多种做法
对于一个询问 \(a, b\) ,它的答案就是所有经过时刻中区间 \([a, b]\) 内的值全为 \(1\) 的情况数。
所以可以考虑维护极大连通 \(1\) 的子段, 设其出现时间为 \(t\) ,那么就会有一个三元组 \(\left(l,r,t\right)\) 。
对于一个询问 \(a,b\) 以及时刻 \(i\) ,要求的就是满足 \(a \geq l, \; b \leq r, \; i \geq t\) 并且没有被删除的三元组 \(\left(l,r,t\right)\) 的个数。
问题转化为三维偏序,可以大力树套树 或者 直接上CDQ维护。
同样,增加/删除/询问 这三种操作的顺序要搞清楚。
关于维护极大连通 \(1\) 的子段,可以使用 ODT 。
不过本题中也可以不使用。
既然维护区间有点难度,那就可以维护所有 \(0\) 的点的位置,跑一遍初始化后同样可以快速找到需要 删除/增加 的区间。
(后注:这是因为本题中修改是单点修改,可以不需要区间推平(assign)这个操作。)
不过值得注意的是,本题中三元组对答案的贡献与普通偏序问题稍有区别。
满足条件并且没有被删除的三元组 \(\left(l, r, t\right)\) 对询问 \(\left(a, b, i\right)\) 的贡献为 \(i-t\) 。
不过注意到无论在 \(x\) 时刻是增加还是删除一个三元组,对该询问的贡献都只是加上或者减去 \(i-x\) 。
(出现时间为 \(t_1\) ,消失时间为 \(t_2\),那么有 \(ans=t_2-t_1=+(i-t_1)-(i-t_2)\),其余情况同理)
所以CDQ的时候开两个树状数组分别存 \(\sum 1\) 和 \(\sum x\) 即可。
时间复杂度 \(O\left(n \log^2 n\right)\) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9') && c!='q' && c!='t') c=getchar(); if(c=='q') return 2; else if(c=='t') return 0; register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } struct _query { int type,l,r,time; }res[2050505],tres[2050505]; int lq,lans,ans[305050]; int N,fs[305050],fo[305050]; #define _lowbit(_x) ((_x)&-(_x)) int __x,__ans; #define update(_f,_x,_val) \ ({ \ __x=_x; \ while(__x <= N) \ { \ _f[__x]+=_val; \ __x+=_lowbit(__x); \ } \ }) #define query(_f,_x) \ ({ \ __ans=0,__x=_x; \ while(__x) \ { \ __ans+=_f[__x]; \ __x-=_lowbit(__x); \ } \ __ans; \ }) void CDQ_Divide(register int l,register int r) { if(l==r) return; register int mid=(l+r)>>1,tl=l,tr=mid+1; CDQ_Divide(l,mid),CDQ_Divide(mid+1,r); register int j=l; for(register int i=mid+1;i<=r;i++) { while(j<=mid && res[j].l<=res[i].l) { if(res[j].type < 2) update(fs,res[j].r,res[j].type), update(fo,res[j].r,res[j].type*res[j].time); j++; } if(res[i].type >= 2) ans[res[i].type]+=(query(fs,N)-query(fs,res[i].r-1))*res[i].time -(query(fo,N)-query(fo,res[i].r-1)); } for(register int i=l;i<j;i++) if(res[i].type < 2) update(fs,res[i].r,-res[i].type), update(fo,res[i].r,-res[i].type*res[i].time); for(register int i=l;i<=r;i++) if(tr>r || (tl<=mid && res[tl].l<res[tr].l)) tres[i]=res[tl++]; else tres[i]=res[tr++]; for(register int i=l;i<=r;i++) res[i]=tres[i]; } char s[305050]; typedef __gnu_pbds::tree<int,__gnu_pbds::null_type> _t; typedef _t::point_iterator _it; _t pre; int main() { register int N=getnum(),Q=getnum(); ::N=N; while((s[1]=getchar())!='0' && s[1]!='1'); for(register int i=2;i<=N;i++) s[i]=getchar(); pre.insert(0),pre.insert(N+1); for(register int i=1;i<=N;i++) if(s[i]=='0') pre.insert(i); else { res[++lq]=(_query){1,i,0,0}; while(i<=N && s[i]=='1') i++; res[lq].r=(--i); } lans=1; for(register int i=1,x;i<=Q;i++) if(getnum()==2) res[++lq]=(_query){++lans,getnum(),getnum()-1,i}; else if(s[x=getnum()]=='0') { _it pit=pre.find(x),nit=pit--,it=nit++; if(*pit+1 <= x-1) res[++lq]=(_query){-1,*pit+1,x-1,i}; if(x+1 <= *nit-1) res[++lq]=(_query){-1,x+1,*nit-1,i}; res[++lq]=(_query){1,*pit+1,*nit-1,i}; s[x]='1',pre.erase(it); } else { _it pit=pre.insert(x).first,nit=pit--,it=nit++; res[++lq]=(_query){-1,*pit+1,*nit-1,i}; if(*pit+1 <= x-1) res[++lq]=(_query){1,*pit+1,x-1,i}; if(x+1 <= *nit-1) res[++lq]=(_query){1,x+1,*nit-1,i}; s[x]='0'; } CDQ_Divide(1,lq); for(register int i=2;i<=lans;i++) printf("%d\n",ans[i]); return 0; } |