Gorgeous Sequence 题解 (小清新线段树)

这道题被学长称为“科幻题”

题面

事实上，并不是做法科幻，而是“为什么能这么做？”的解释非常科幻

换句话说，复杂度分析灰常诡异以至于吉如一大佬当场吃书

线段树维护的量：区间和sum，区间最大值max1，区间次大值max2，最大值出现次数cnt。

现在假设区间[l,r]对x取min，那么有如下三种情况：

1.max1<=x，不用修改，return ；

2.max2<x<max1,修改只会影响所有最大值，sum+=cnt*(max1-x)，更新max1打标记；

3.max2>=x,暴力递归修改左右儿子.

吃书后只能保证复杂度O(nlog²n)

  1 #include<cstdio>
  2 #include<cstring>
  3 #define ls(k) k<<1
  4 #define rs(k) k<<1|1
  5 
  6 const int L=1<<20|1;
  7 char buffer[L],*S,*TT;
  8 #define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,L,stdin),S==TT))?EOF:*S++)
  9 
 10 const int N=1000005;
 11 typedef long long ll;
 12 int max(int a,int b){return a>b?a:b;}
 13 int min(int a,int b){return a<b?a:b;}
 14 int T,n,m,a[N];
 15 struct segment_tree
 16 {
 17     int max1[N<<2],max2[N<<2],cnt[N<<2];
 18     ll sum[N<<2];
 19     void up(int k)
 20     {
 21         sum[k]=sum[ls(k)]+sum[rs(k)];
 22         max1[k]=max(max1[ls(k)],max1[rs(k)]);
 23         max2[k]=max(max2[ls(k)],max2[rs(k)]);
 24         cnt[k]=0;
 25         if(max1[ls(k)]!=max1[rs(k)])max2[k]=max(max2[k],min(max1[ls(k)],max1[rs(k)]));
 26         cnt[k]+=(max1[k]==max1[ls(k)]?cnt[ls(k)]:0);
 27         cnt[k]+=(max1[k]==max1[rs(k)]?cnt[rs(k)]:0);
 28     }
 29     void tag(int k,int val)
 30     {
 31         if(val>=max1[k])return ;
 32         sum[k]+=(ll)(val-max1[k])*cnt[k];
 33         max1[k]=val;
 34     }
 35     void down(int k)
 36     {
 37         tag(ls(k),max1[k]);
 38         tag(rs(k),max1[k]);
 39     }
 40     void build(int k,int l,int r)
 41     {
 42         if(l==r)
 43         {
 44             sum[k]=max1[k]=a[l];
 45             cnt[k]=1;max2[k]=-1;
 46             return ;
 47         }
 48         int mid=l+r>>1;
 49         build(ls(k),l,mid);
 50         build(rs(k),mid+1,r);
 51         up(k);
 52     }
 53     void change(int k,int l,int r,int L,int R,int val)
 54     {
 55         if(val>=max1[k])return ;
 56         if(L<=l&&R>=r&&val>max2[k])
 57         {
 58             tag(k,val);
 59             return ;
 60         }
 61         int mid=l+r>>1;down(k);
 62         if(L<=mid)change(ls(k),l,mid,L,R,val);
 63         if(R>mid)change(rs(k),mid+1,r,L,R,val);
 64         up(k);
 65     }
 66     ll qsum(int k,int l,int r,int L,int R)
 67     {
 68         if(L<=l&&R>=r)return sum[k];
 69         int mid=l+r>>1;
 70         down(k);ll res=0;
 71         if(L<=mid)res+=qsum(ls(k),l,mid,L,R);
 72         if(R>mid)res+=qsum(rs(k),mid+1,r,L,R);
 73         return res;
 74     }
 75     int qmax(int k,int l,int r,int L,int R)
 76     {
 77         if(L<=l&&R>=r)return max1[k];
 78         down(k);
 79         int mid=l+r>>1,ans=-1;
 80         if(L<=mid)ans=max(ans,qmax(ls(k),l,mid,L,R));
 81         if(R>mid)ans=max(ans,qmax(rs(k),mid+1,r,L,R));
 82         return ans;
 83     }
 84 }seg;
 85 inline int read()
 86 {
 87     int x=0,f=1;char ch=getchar();
 88     while(ch<'0'||ch>'9')
 89     {if(ch=='-')f=-1;ch=getchar();}
 90     while(ch>='0'&&ch<='9')
 91     {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
 92     return x*f;
 93 }
 94 void work()
 95 {
 96     n=read();m=read();
 97     for(int i=1;i<=n;i++)a[i]=read();
 98     seg.build(1,1,n);
 99     while(m--)
100     {
101         int op=read(),l=read(),r=read();
102         if(op==0)
103         {
104             int val=read();
105             seg.change(1,1,n,l,r,val);
106         }
107         else if(op==1)printf("%d
",seg.qmax(1,1,n,l,r));
108         else if(op==2)printf("%lld
",seg.qsum(1,1,n,l,r));
109     }
110 }
111 int main()
112 {
113     T=read();
114     while(T--)work();
115     return 0;
116 }

View Code