LOJ#6504. 「雅礼集训 2018 Day5」Convex（回滚莫队）

今天药忘吃喽~ 2021-12-23 05:45 218阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

因为并不强制在线，我们可以考虑莫队

然而莫队的时候有个问题，删除很简单，除去它和前驱后继的贡献即可。但是插入的话却要找到前驱后继再插入，非常麻烦

那么我们把它变成只删除的回滚莫队就好了

不知道回滚莫队的可以看看[这里][Link 2]

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define 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) 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 C=-1,Z=0; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} void print(R ll x){ if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=2e5+5; struct node{ int x,y;double ang; inline ll operator *(const node &b)const{return 1ll*x*b.y-1ll*y*b.x;} }p[N]; ll ans[N],res;int id[N],rt[N],Pre[N],nxt[N]; struct query{ int l,r,id; inline bool operator <(const query &b)const{return rt[l]==rt[b.l]?r>b.r:l<b.l;} }q[N]; inline bool cmp(const int &a,const int &b){return p[a].ang<p[b].ang;} int n,m,s; void ins(int x){ int u=Pre[x],v=nxt[x]; res-=p[u]*p[v],res+=p[u]*p[x],res+=p[x]*p[v]; Pre[v]=nxt[u]=x; } void del(int x){ int u=Pre[x],v=nxt[x]; res+=p[u]*p[v],res-=p[u]*p[x],res-=p[x]*p[v]; Pre[v]=u,nxt[u]=v; } int main(){ // freopen("testdata.in","r",stdin); n=read(),m=read(),s=387; fp(i,1,n)p[i].x=read(),p[i].y=read(),p[i].ang=atan2(p[i].y,p[i].x),id[i]=i,rt[i]=(i-1)/s+1; sort(id+1,id+1+n,cmp); fp(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i; sort(q+1,q+1+m); for(R int k=1,i=1;k<=(n-1)/s+1&&i<=m;++k)if(rt[q[i].l]==k){ int bg=(k-1)*s+1,l=bg,r=n,lst=0,fir;res=0; fp(j,1,n)if(id[j]>=bg){ Pre[id[j]]=lst; !lst?fir=id[j]:(nxt[lst]=id[j],res+=p[lst]*p[id[j]]); lst=id[j]; } nxt[lst]=fir,Pre[fir]=lst,res+=p[lst]*p[fir]; while(i<=m&&rt[q[i].l]==k){ while(r>q[i].r)del(r--); while(l<q[i].l)del(l++); ans[q[i].id]=res; while(l>bg)ins(--l); ++i; } } fp(i,1,m)print(ans[i]); return Ot(),0; }

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

[Link 1]: https://loj.ac/problem/6504
[Link 2]: https://www.cnblogs.com/bztMinamoto/p/10375035.html