LOJ#503. 「LibreOJ β Round」ZQC 的课堂（容斥+FHQTreap）

谁借莪１个温暖的怀抱￠ 2021-12-23 05:49 138阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

首先\\(x\\)和\\(y\\)两维互相独立，可以分开考虑，我们以\\(x\\)为例

我们把\\(x\\)做个前缀和，那么就是问有多少\\(i\\)满足\\(s\_is\_\{i-1\}<0\\)，其中\\(s\_0=1\\)。这个条件等价于\\(\\max(s\_i,s\_\{i-1\})>0\\)且\\(\\min(s\_i,s\_\{i-1\})<0\\)。我们可以容斥一下，就是总数减去\\(\\max(s\_i,s\_\{i-1\})<0\\)的个数减去\\(\\min(s\_i,s\_\{i-1\})>0\\)的个数

注意到一次单点修改会使一个点到结尾的\\(s\_i\\)区间加，而对应的\\(\\max(s\_i,s\_\{i+1\}),\\max(s\_\{i+1\},s\_\{i+2\})\\)之类的可以直接加上这个值，但前面的不行。我们记录一个偏移量，并且开一个平衡树，平衡树里只放指针右边的元素，那么一次修改不会影响前面，我们可以在移动指针的时候顺便维护答案，而指针右边的答案在平衡树里找就可以了

//minamoto #include<bits/stdc++.h> #define R register #define inline __inline__ __attribute__((always_inline)) #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } char sr[1<<21],z[20];int K=-1,Z=0; inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;} void print(R int x){ if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++K]=z[Z],--Z);sr[++K]='\n'; } inline char getop(){char ch;while((ch=getc())>'Z'||ch<'A');return ch;} unsigned int aaa=19260817; inline unsigned int rd(){aaa^=aaa>>15,aaa+=aaa<<12,aaa^=aaa>>3;return aaa;} inline int max(R int x,R int y){return x>y?x:y;} inline int min(R int x,R int y){return x<y?x:y;} const int N=2e5+5; struct node;typedef node* ptr; struct node{ ptr lc,rc;int sz,v;unsigned int pr; inline ptr init(R int val){return sz=1,v=val,pr=rd(),this;} inline ptr upd(){return sz=lc->sz+rc->sz+1,this;} }; struct Treap{ node e[N],*rt=e,*pp=e; inline ptr newnode(R int v){return ++pp,pp->lc=pp->rc=e,pp->init(v);} void split(ptr p,int k,ptr &s,ptr &t){ if(p==e)return s=t=e,void(); if(p->v<=k)s=p,split(p->rc,k,p->rc,t); else t=p,split(p->lc,k,s,p->lc); p->upd(); } ptr merge(ptr s,ptr t){ if(s==e)return t;if(t==e)return s; if(s->pr<t->pr)return s->rc=merge(s->rc,t),s->upd(); return t->lc=merge(s,t->lc),t->upd(); } void push(int k){ ptr s,t; split(rt,k,s,t),rt=merge(merge(s,newnode(k)),t); } void pop(int k){ ptr s,t,p,q; split(rt,k,s,t),split(s,k-1,p,q),q=merge(q->lc,q->rc); rt=merge(merge(p,q),t); } int les(int k){ ptr s,t;int now; split(rt,k-1,s,t),now=s->sz; return rt=merge(s,t),now; } int gre(int k){ ptr s,t;int now; split(rt,k,s,t),now=t->sz; return rt=merge(s,t),now; } Treap(){e->lc=e->rc=e;} }sx[2],sy[2]; int nx[N],ny[N],X,Y,dx,dy,p,ansx,ansy,n; void Ri(){ if(p==n)return;++p; sx[0].pop(min(X,X+nx[p])-dx),sx[1].pop(max(X,X+nx[p])-dx), sy[0].pop(min(Y,Y+ny[p])-dy),sy[1].pop(max(Y,Y+ny[p])-dy); if(X*(X+nx[p])<0)++ansx;if(Y*(Y+ny[p])<0)++ansy; X+=nx[p],Y+=ny[p]; } void Le(){ if(p==1)return;X-=nx[p],Y-=ny[p]; if(X*(X+nx[p])<0)--ansx;if(Y*(Y+ny[p])<0)--ansy; sx[0].push(min(X,X+nx[p])-dx),sx[1].push(max(X,X+nx[p])-dx), sy[0].push(min(Y,Y+ny[p])-dy),sy[1].push(max(Y,Y+ny[p])-dy); --p; } void modify(){ int x=read(),y=read(); if(X*(X-nx[p])<0)--ansx;if(Y*(Y-ny[p])<0)--ansy; X+=x-nx[p],Y+=y-ny[p],dx+=x-nx[p],dy+=y-ny[p],nx[p]=x,ny[p]=y; if(X*(X-x)<0)++ansx;if(Y*(Y-y)<0)++ansy; } inline int query(){return n-p-sx[0].gre(-dx)-sx[1].les(-dx)+n-p-sy[0].gre(-dy)-sy[1].les(-dy)+ansx+ansy;} int main(){ // freopen("testdata.in","r",stdin); n=read(),X=Y=1; fp(i,1,n){ nx[i]=read(),ny[i]=read(); sx[0].push(min(X,X+nx[i])),sx[1].push(max(X,X+nx[i])); sy[0].push(min(Y,Y+ny[i])),sy[1].push(max(Y,Y+ny[i])); X+=nx[i],Y+=ny[i]; } X=Y=1,p=0,Ri(); for(int q=read();q;--q){ char op=getop(); switch(op){ case 'F':Ri();break; case 'B':Le();break; case 'C':modify();break; case 'Q':print(query());break; } } return Ot(),0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10890637.html

[Link 1]: https://loj.ac/problem/503