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(nlogn)

 #include<cstdio>

 #include<cstring>

 #define ls(k) k<<1

 #define rs(k) k<<1|1

 const int L=<<|;

 char buffer[L],*S,*TT;

 #define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,L,stdin),S==TT))?EOF:*S++)

 const int N=;

 typedef long long ll;

 int max(int a,int b){return a>b?a:b;}

 int min(int a,int b){return a<b?a:b;}

 int T,n,m,a[N];

 struct segment_tree

 {

     int max1[N<<],max2[N<<],cnt[N<<];

     ll sum[N<<];

     void up(int k)

     {

         sum[k]=sum[ls(k)]+sum[rs(k)];

         max1[k]=max(max1[ls(k)],max1[rs(k)]);

         max2[k]=max(max2[ls(k)],max2[rs(k)]);

         cnt[k]=;

         if(max1[ls(k)]!=max1[rs(k)])max2[k]=max(max2[k],min(max1[ls(k)],max1[rs(k)]));

         cnt[k]+=(max1[k]==max1[ls(k)]?cnt[ls(k)]:);

         cnt[k]+=(max1[k]==max1[rs(k)]?cnt[rs(k)]:);

     }

     void tag(int k,int val)

     {

         if(val>=max1[k])return ;

         sum[k]+=(ll)(val-max1[k])*cnt[k];

         max1[k]=val;

     }

     void down(int k)

     {

         tag(ls(k),max1[k]);

         tag(rs(k),max1[k]);

     }

     void build(int k,int l,int r)

     {

         if(l==r)

         {

             sum[k]=max1[k]=a[l];

             cnt[k]=;max2[k]=-;

             return ;

         }

         int mid=l+r>>;

         build(ls(k),l,mid);

         build(rs(k),mid+,r);

         up(k);

     }

     void change(int k,int l,int r,int L,int R,int val)

     {

         if(val>=max1[k])return ;

         if(L<=l&&R>=r&&val>max2[k])

         {

             tag(k,val);

             return ;

         }

         int mid=l+r>>;down(k);

         if(L<=mid)change(ls(k),l,mid,L,R,val);

         if(R>mid)change(rs(k),mid+,r,L,R,val);

         up(k);

     }

     ll qsum(int k,int l,int r,int L,int R)

     {

         if(L<=l&&R>=r)return sum[k];

         int mid=l+r>>;

         down(k);ll res=;

         if(L<=mid)res+=qsum(ls(k),l,mid,L,R);

         if(R>mid)res+=qsum(rs(k),mid+,r,L,R);

         return res;

     }

     int qmax(int k,int l,int r,int L,int R)

     {

         if(L<=l&&R>=r)return max1[k];

         down(k);

         int mid=l+r>>,ans=-;

         if(L<=mid)ans=max(ans,qmax(ls(k),l,mid,L,R));

         if(R>mid)ans=max(ans,qmax(rs(k),mid+,r,L,R));

         return ans;

     }

 }seg;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>'')

     {if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<='')

     {x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 void work()

 {

     n=read();m=read();

     for(int i=;i<=n;i++)a[i]=read();

     seg.build(,,n);

     while(m--)

     {

         int op=read(),l=read(),r=read();

         if(op==)

         {

             int val=read();

             seg.change(,,n,l,r,val);

         }

         else if(op==)printf("%d\n",seg.qmax(,,n,l,r));

         else if(op==)printf("%lld\n",seg.qsum(,,n,l,r));

     }

 }

 int main()

 {

     T=read();

     while(T--)work();

     return ;

 }