[loj3146]路灯

显然，能从$l$到$r$当且仅当$[l,r)$中的灯全部都亮，以下不妨令询问的$r$全部减1

当修改节点$x$时，找到包含$x$的极大的灯（除$x$以外）全部都亮的区间$[l,r]$，即令$l_{0}\in [l,x]$且$r_{0}\in [x,r]$的询问答案加上或减去$\Delta t$（其中$\Delta t$为该询问时刻-当前修改时刻）

可以将其看作一个一次函数的形式（关于询问时刻，当然斜率只为0或1），那么问题即变为支持矩阵加（可负）和单点查询，差分后也相当于是三维偏序问题，cdq分治+线段树即可

时间复杂度为$o(n\log^{2}n)$，可以通过

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 300005

  4 #define L (k<<1)

  5 #define R (L+1)

  6 #define mid (l+r>>1)

  7 #define pii pair<int,int>

  8 #define mp make_pair

  9 #define fi first

 10 #define se second

 11 struct Data{

 12     int p,x,y;

 13     pii z;

 14 }a[N<<3];

 15 vector<Data>v;

 16 pii sum[N<<2];

 17 int E,n,m,q,t,x,y,vis[N],ans[N],f[N<<2];

 18 char s[N];

 19 bool cmp(Data x,Data y){

 20     return (x.x>y.x)||(x.x==y.x)&&(x.p<y.p);

 21 }

 22 pii merge(pii x,pii y){

 23     return mp(x.fi+y.fi,x.se+y.se);

 24 }

 25 void update(int k,int l,int r,int x,pii y){

 26     sum[k]=merge(sum[k],y);

 27     if (l==r)return;

 28     if (x<=mid)update(L,l,mid,x,y);

 29     else update(R,mid+1,r,x,y);

 30 }

 31 pii query(int k,int l,int r,int x,int y){

 32     if ((l>y)||(x>r))return mp(0,0);

 33     if ((x<=l)&&(r<=y))return sum[k];

 34     return merge(query(L,l,mid,x,y),query(R,mid+1,r,x,y));

 35 }

 36 void update(int k,int l,int r,int x){

 37     if (l==r){

 38         f[k]^=1;

 39         return;

 40     }

 41     if (x<=mid)update(L,l,mid,x);

 42     else update(R,mid+1,r,x);

 43     f[k]=f[L]+f[R];

 44 }

 45 int getl(int k,int l,int r,int x){

 46     if ((l>=x)||(r<x)&&(f[k]==r-l+1))return 0;

 47     if (l==r)return l;

 48     int ans=getl(R,mid+1,r,x);

 49     if (ans)return ans;

 50     return getl(L,l,mid,x);

 51 }

 52 int getr(int k,int l,int r,int x){

 53     if ((r<=x)||(l>x)&&(f[k]==r-l+1))return n+1;

 54     if (l==r)return l;

 55     int ans=getr(L,l,mid,x);

 56     if (ans<=n)return ans;

 57     return getr(R,mid+1,r,x);

 58 }

 59 void update(int k,int id){

 60     update(1,1,n,k);

 61     vis[k]^=1;

 62     int l=getl(1,1,n,k)+1,r=getr(1,1,n,k)-1;

 63     pii o1=mp(1,-id),o2=mp(-1,id);

 64     if (!vis[k])swap(o1,o2);

 65     a[++t]=Data{0,k,r,o1};

 66     if (k>1)a[++t]=Data{0,k,k-1,o2};

 67     if (l>1)a[++t]=Data{0,l-1,r,o2};

 68     if ((k>1)&&(l>1))a[++t]=Data{0,l-1,k-1,o1};

 69 }

 70 void query(int x,int y,int id){

 71     a[++t]=Data{1,x,y,mp(id,++q)};

 72 }

 73 void calc(int l,int r){

 74     if (l==r)return;

 75     v.clear();

 76     for(int i=l;i<=mid;i++)

 77         if (!a[i].p)v.push_back(a[i]);

 78     for(int i=mid+1;i<=r;i++)

 79         if (a[i].p)v.push_back(a[i]);

 80     sort(v.begin(),v.end(),cmp);

 81     for(int i=0;i<v.size();i++)

 82         if (!v[i].p)update(1,1,n,v[i].y,v[i].z);

 83         else{

 84             pii o=query(1,1,n,v[i].y,n);

 85             ans[v[i].z.se]+=o.fi*v[i].z.fi+o.se;

 86         }

 87     for(int i=0;i<v.size();i++)

 88         if (!v[i].p)update(1,1,n,v[i].y,mp(-v[i].z.fi,-v[i].z.se));

 89     calc(l,mid);

 90     calc(mid+1,r);

 91 }

 92 int main(){

 93     scanf("%d%d%s",&n,&m,s+1);

 94     for(int i=1;i<=n;i++)

 95         if (s[i]=='1')update(i,0);

 96     for(int i=1;i<=m;i++){

 97         scanf("%s%d",s,&x);

 98         if (s[0]=='t')update(x,i);

 99         else{

100             scanf("%d",&y);

101             query(x,y-1,i);

102         }

103     }

104     calc(1,t);

105     for(int i=1;i<=q;i++)printf("%d\n",ans[i]);

106 }

巴特西

[loj3146]路灯

最新文章

热门文章