Description

Input

Sample Input

10 9
3580 8597 508 9110 9162 9973 6017 1942 989 646
1 3 4 405
4 3 5
5 6 7
6 4 9
7 5 7
2 1 8 9623
5 1 6
4 2 7
3 7 7 8581

Output

Sample Output

19590
6017
9973
1
-8710
-13561

Solution

• 超級碼農(nóng)題！！！

• 顯然線段樹，第①②④⑤⑥問都可以輕易處理出來

• 對于第③問，只需維護一下標志數(shù)組，也不難處理

• 而本題的關(guān)鍵是第⑦問！

• 對于一個區(qū)間，記錄以下一些量：

  1.最左邊的數(shù)
  2.最右邊的數(shù)
  3.以最左邊為起點往右延伸個數(shù)
  4.以最右邊為起點往左延伸個數(shù)
  5.答案（最長子串）

• 這樣合并方法就很顯然了！

• 為處理方便也可記錄區(qū)間元素個數(shù)，時間復(fù)雜度 O(Nlogn)

Code

#include<cstdio> #include<algorithm> using namespace std; const int N=100001,MX=1e9; typedef long long LL; struct data {int max,min,left,right,lnum,rnum,len,cnt;LL sum; }f[8*N]; int n,q,num,sum; int a[N],c[8*N],d[8*N]; LL ans; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; } inline void updata(int v) {int ls=2*v,rs=ls+1;f[v].max=max(f[ls].max,f[rs].max);f[v].min=min(f[ls].min,f[rs].min);f[v].sum=f[ls].sum+f[rs].sum;f[v].lnum=f[ls].lnum,f[v].rnum=f[rs].rnum;f[v].left=f[ls].left,f[v].right=f[rs].right;f[v].len=max(f[ls].len,f[rs].len);if(f[ls].rnum==f[rs].lnum){f[v].len=max(f[v].len,f[ls].right+f[rs].left);if(f[ls].left==f[ls].cnt) f[v].left+=f[rs].left;if(f[rs].right==f[rs].cnt) f[v].right+=f[ls].right;} } inline void modify(int v) {int ls=v*2,rs=v*2+1;if(d[v]==1){f[v].max+=c[v],f[v].min+=c[v];f[v].lnum+=c[v],f[v].rnum+=c[v];f[v].sum+=f[v].cnt*c[v];c[ls]+=c[v],c[rs]+=c[v];if(!d[ls]) d[ls]=1;if(!d[rs]) d[rs]=1;c[v]=d[v]=0;}elseif(d[v]==2){f[v].max=f[v].min=f[v].lnum=f[v].rnum=c[v];f[v].sum=f[v].cnt*c[v];f[v].len=f[v].left=f[v].right=f[v].cnt;c[ls]=c[rs]=c[v];d[ls]=d[rs]=2;c[v]=d[v]=0;} } inline void make(int v,int l,int r) {if(l==r){f[v].sum=f[v].max=f[v].min=f[v].lnum=f[v].rnum=a[l];f[v].len=f[v].left=f[v].right=f[v].cnt=1;return;}int mid=(l+r)>>1,ls=2*v,rs=ls+1;make(ls,l,mid),make(rs,mid+1,r);f[v].cnt=f[ls].cnt+f[rs].cnt;updata(v); } inline void find(int v,int l,int r,int x,int y,int pd) {if(l==x && r==y){if(pd==4) ans+=f[v].sum; elseif(pd==5) ans=min(ans,(LL)f[v].min); else ans=max(ans,(LL)f[v].max);return;}int mid=(l+r)>>1,ls=2*v,rs=ls+1;modify(ls),modify(rs);if(y<=mid) find(ls,l,mid,x,y,pd); elseif(x>mid) find(rs,mid+1,r,x,y,pd); else{find(ls,l,mid,x,mid,pd);find(rs,mid+1,r,mid+1,y,pd);} } inline int find_all(int v,int l,int r,int x,int y) {if(l==x && r==y) return f[v].len;int mid=(l+r)>>1,ls=2*v,rs=ls+1;modify(ls),modify(rs);if(y<=mid) return find_all(ls,l,mid,x,y); elseif(x>mid) return find_all(rs,mid+1,r,x,y); else{int sum=max(find_all(ls,l,mid,x,mid),find_all(rs,mid+1,r,mid+1,y));if(f[ls].rnum==f[rs].lnum) sum=max(sum,min(f[ls].right,mid-x+1)+min(f[rs].left,y-mid));return sum;} } inline void change(int v,int l,int r,int x,int y,int z) {if(l==x && r==y){c[v]=z,d[v]=1;modify(v);return;}int mid=(l+r)>>1,ls=2*v,rs=ls+1;modify(ls),modify(rs);if(y<=mid) change(ls,l,mid,x,y,z); elseif(x>mid) change(rs,mid+1,r,x,y,z); else{change(ls,l,mid,x,mid,z);change(rs,mid+1,r,mid+1,y,z);}updata(v); } inline void change_all(int v,int l,int r,int x,int y,int z) {if(l==x && r==y){c[v]=z,d[v]=2;modify(v);return;}int mid=(l+r)>>1,ls=2*v,rs=ls+1;modify(ls),modify(rs);if(y<=mid) change_all(ls,l,mid,x,y,z); elseif(x>mid) change_all(rs,mid+1,r,x,y,z); else{change_all(ls,l,mid,x,mid,z);change_all(rs,mid+1,r,mid+1,y,z);}updata(v); } int main() {n=read(),q=read();for(int i=1;i<=n;i++) a[i]=read();make(1,1,n);while(q--){int t=read(),l=read(),r=read();if(t==7) printf("%d\n",find_all(1,1,n,l,r)); elseif(t<=3){int v=read();if(t==3) change_all(1,1,n,l,r,v); else{if(t==2) v=-v;change(1,1,n,l,r,v);}}else{if(t==4) ans=0; elseif(t==5) ans=MX; else ans=-MX;find(1,1,n,l,r,t);printf("%lld\n",ans);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 4933. 【NOIP2017提高组模拟12.24】C的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。