segment tree beats模板题

在线段树上维护子树内最大值及个数、严格次大值和区间和，即可支持$o(\log n)$查询

修改时，搜索至完全覆盖的区间后再分类讨论：

1.若修改值大于严格次大值，可以打上懒标记并维护上述信息

2.若修改值不超过严格次大值，继续递归下去

（另外，该信息显然也可以up维护）

考虑这样的修改复杂度，定义势能为线段树所有节点对应区间内元素种类数和，那么修改时的第2种情况，必然会导致该区间对势能贡献减小1，因此均摊复杂度为$o(\log n)$

势能范围为$[0,n\log n]$，因此时间复杂度为$o((n+m)\log n)$，可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 1000005
 4 #define ll long long
 5 #define L (k<<1)
 6 #define R (L+1)
 7 #define mid (l+r>>1)
 8 int t,n,m,p,x,y,z,a[N],mx[N<<2],cnt[N<<2],cmx[N<<2],tag[N<<2];
 9 ll sum[N<<2];
10 void upd(int k,int x){
11     if (mx[k]<=x)return;
12     sum[k]+=(ll)cnt[k]*(x-mx[k]);
13     tag[k]=mx[k]=x;
14 }
15 void up(int k){
16     mx[k]=max(mx[L],mx[R]),sum[k]=sum[L]+sum[R];
17     cnt[k]=0,cmx[k]=max(cmx[L],cmx[R]);
18     if (mx[k]==mx[L])cnt[k]+=cnt[L];
19     else cmx[k]=max(cmx[k],mx[L]);
20     if (mx[k]==mx[R])cnt[k]+=cnt[R];
21     else cmx[k]=max(cmx[k],mx[R]);
22 }
23 void down(int k){
24     if (tag[k]>=0){
25         upd(L,tag[k]);
26         upd(R,tag[k]);
27         tag[k]=-1;
28     }
29 }
30 void build(int k,int l,int r){
31     tag[k]=-1;
32     if (l==r){
33         mx[k]=sum[k]=a[l];
34         cnt[k]=1,cmx[k]=-1;
35         return;
36     }
37     build(L,l,mid);
38     build(R,mid+1,r);
39     up(k);
40 }
41 void update(int k,int l,int r,int x,int y,int z){
42     if ((l>y)||(x>r))return;
43     if ((x<=l)&&(r<=y)&&(cmx[k]<z)){
44         upd(k,z);
45         return;
46     }
47     down(k);
48     update(L,l,mid,x,y,z);
49     update(R,mid+1,r,x,y,z);
50     up(k);
51 }
52 int query_max(int k,int l,int r,int x,int y){
53     if ((l>y)||(x>r))return -1;
54     if ((x<=l)&&(r<=y))return mx[k];
55     down(k);
56     return max(query_max(L,l,mid,x,y),query_max(R,mid+1,r,x,y));
57 }
58 ll query_sum(int k,int l,int r,int x,int y){
59     if ((l>y)||(x>r))return 0;
60     if ((x<=l)&&(r<=y))return sum[k];
61     down(k);
62     return query_sum(L,l,mid,x,y)+query_sum(R,mid+1,r,x,y);
63 }
64 int main(){
65     scanf("%d",&t);
66     while (t--){
67         scanf("%d%d",&n,&m);
68         for(int i=1;i<=n;i++)scanf("%d",&a[i]);
69         build(1,1,n);
70         for(int i=1;i<=m;i++){
71             scanf("%d%d%d",&p,&x,&y);
72             if (!p){
73                 scanf("%d",&z);
74                 update(1,1,n,x,y,z);
75             }
76             if (p==1)printf("%d\n",query_max(1,1,n,x,y));
77             if (p==2)printf("%lld\n",query_sum(1,1,n,x,y));
78         }
79     }
80     return 0;
81 } 

View Code