题目描述
http://uoj.ac/problem/88
题解
维护两颗线段树, 维护最大值和最小值, 因为每次只有单点查询, 所以可以直接在区间插入线段就可以了.
注意卡常, 不要写 STL, 用链表把同类修改串起来就好了.
代码
- %:pragma GCC optimize(2)
- %:pragma GCC optimize(3)
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #include<vector>
- #include<cstdlib>
- #define N 600009
- using namespace std;
- typedef long long ll;
- struct node{ll tim,x;};
- int n,m,la[N],pre[N];
- ll t[N],pos[N],b[N],top,now[N],k[N],x[N],tag[N];
- char s[10];
- inline ll rd(){
- ll x=0;char c=getchar();bool f=0;
- while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
- while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
- return f?-x:x;
- }
- inline ll calc(ll l,ll r,ll x,ll k){return x+k*(r-l);}
- struct segment1{
- struct seg{
- int l,r;ll x,k;
- }tr[N<<1];
- int tot,root;
- void work(int &cnt,int l,int r,ll x,ll k){
- if(!cnt)cnt=++tot;
- int mid=(l+r)>>1;
- if(!tr[cnt].x&&!tr[cnt].k){tr[cnt].x=x;tr[cnt].k=k;return;}
- ll x1=calc(b[l],b[mid],x,k),x2=calc(b[l],b[mid],tr[cnt].x,tr[cnt].k);
- if(x1>=x2){
- ll xx=tr[cnt].x,kk=tr[cnt].k;
- tr[cnt].x=x;tr[cnt].k=k;
- x=xx;k=kk;
- }
- if(l==r)return;
- if(x>=tr[cnt].x)work(tr[cnt].l,l,mid,x,k);else work(tr[cnt].r,mid+1,r,x+(b[mid+1]-b[l])*k,k);
- }
- void upd(int &cnt,int l,int r,int L,int R,ll x,ll k){
- if(!cnt)cnt=++tot;
- if(l>=L&&r<=R){
- work(cnt,l,r,x+(b[l]-b[L])*k,k);
- return;
- }
- int mid=(l+r)>>1;
- if(mid>=L)upd(tr[cnt].l,l,mid,L,R,x,k);
- if(mid<R)upd(tr[cnt].r,mid+1,r,L,R,x,k);
- }
- }T1;
- struct segment2{
- struct seg{
- int l,r;ll x,k;
- }tr[N<<1];
- int tot,root;
- void work(int &cnt,int l,int r,ll x,ll k){
- if(!cnt)cnt=++tot;
- int mid=(l+r)>>1;
- if(!tr[cnt].x&&!tr[cnt].k){tr[cnt].x=x;tr[cnt].k=k;return;}
- ll x1=calc(b[l],b[mid],x,k),x2=calc(b[l],b[mid],tr[cnt].x,tr[cnt].k);
- if(x1<=x2){
- ll xx=tr[cnt].x,kk=tr[cnt].k;
- tr[cnt].x=x;tr[cnt].k=k;
- x=xx;k=kk;
- }
- if(l==r)return;
- if(x<=tr[cnt].x)work(tr[cnt].l,l,mid,x,k);else work(tr[cnt].r,mid+1,r,x+(b[mid+1]-b[l])*k,k);
- }
- void upd(int &cnt,int l,int r,int L,int R,ll x,ll k){
- if(!cnt)cnt=++tot;
- if(l>=L&&r<=R){
- work(cnt,l,r,x+(b[l]-b[L])*k,k);
- return;
- }
- int mid=(l+r)>>1;
- if(mid>=L)upd(tr[cnt].l,l,mid,L,R,x,k);
- if(mid<R)upd(tr[cnt].r,mid+1,r,L,R,x,k);
- }
- }T2;
- ll query(int x){
- int now1=T1.root,now2=T2.root,l=1,r=top;ll ans1=-1e15,ans2=1e15;
- while(now1||now2){
- int mid=(l+r)>>1;
- if(now1)ans1=max(ans1,calc(b[l],b[x],T1.tr[now1].x,T1.tr[now1].k));
- if(now2)ans2=min(ans2,calc(b[l],b[x],T2.tr[now2].x,T2.tr[now2].k));
- if(x<=mid)now1=T1.tr[now1].l,now2=T2.tr[now2].l,r=mid;
- else now1=T1.tr[now1].r,now2=T2.tr[now2].r,l=mid+1;
- }
- ans2=llabs(ans2);
- return max(ans1,ans2);
- }
- int main(){
- n=rd();m=rd();
- for(int i=1;i<=n;++i)pos[i]=rd(),now[i]=0;
- for(int i=1;i<=m;++i){
- t[i]=rd();scanf("%s",s);b[++top]=t[i];
- if(s[0]=='c'){
- k[i]=rd(),x[i]=rd();
- if(!now[k[i]])tag[k[i]]=i;
- pre[i]=now[k[i]];la[now[k[i]]]=i;
- now[k[i]]=i;
- }
- }
- t[m+1]=t[m]+1;b[++top]=0;b[++top]=t[m]+1;
- sort(b+1,b+top+1);
- top=unique(b+1,b+top+1)-b-1;
- for(int i=1;i<=m;++i)t[i]=lower_bound(b+1,b+top+1,t[i])-b;
- for(int i=1;i<=n;++i){
- pre[m+1]=now[i];la[now[i]]=m+1;
- if(!now[i])tag[i]=m+1;
- }
- for(int i=1;i<=n;++i){
- int l=1,r=t[tag[i]];
- T1.upd(T1.root,1,top,l,r,pos[i],0);
- T2.upd(T2.root,1,top,l,r,pos[i],0);
- }
- for(int i=1;i<=m;++i){
- if(k[i]){
- int l=t[i],r=t[la[i]],la=t[pre[i]];
- pos[k[i]]=pos[k[i]]+(b[l]-b[la])*x[pre[i]];
- T1.upd(T1.root,1,top,l,r,pos[k[i]],x[i]);
- T2.upd(T2.root,1,top,l,r,pos[k[i]],x[i]);
- }
- else printf("%lld\n",query(t[i]));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2969308.html