题意简述
维护长度为的序列
,有
组操作。
1.0 x y t:对于
,令
。
2.1 x y:对于
,求
的最大值。
3.2 x y:对于
,求
的总和。
题目解析
小清新数据结构啊……
XYZ大爷和吉利爷太神啦!看了论文终于会做了,太神奇。
考虑线段树,我们发现这道题无法用经典的懒标记维护,怎么办呢?
我们对于线段树的每个结点,维护最大值,最大值出现次数
,严格次大值
和区间和
。
修改时,对于可修改结点,若
1.
:修改对于该区间无效,返回。
2.
:
只对
发生影响,令
并更新区间和,返回。
3.
:无法简单地更新区间和了……
怎么办呢?遇到第三种情况,继续向下DFS直到有结点满足条件。
这个复杂度靠谱吗?一开始是我是怀疑的,看完论文后我真心膜膜膜~~(证明待填...)
另外我想知道,这题现场有人做出来吗……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=(int)(1e6)+5; int a[maxn]; int mx[maxn<<2],mc[maxn<<2],se[maxn<<2]; LL sum[maxn<<2]; inline void pu(int x) { sum[x]=sum[x<<1]+sum[x<<1|1]; mx[x]=max(mx[x<<1],mx[x<<1|1]); se[x]=max(se[x<<1],se[x<<1|1]);mc[x]=0; if(mx[x<<1]!=mx[x<<1|1]) se[x]=max(se[x],min(mx[x<<1],mx[x<<1|1])); if(mx[x]==mx[x<<1]) mc[x]+=mc[x<<1]; if(mx[x]==mx[x<<1|1]) mc[x]+=mc[x<<1|1]; } void dec(int x,int v) { if(v>=mx[x]) return; sum[x]+=1ll*(v-mx[x])*mc[x];mx[x]=v; } inline void pd(int x) { dec(x<<1,mx[x]);dec(x<<1|1,mx[x]); } void build(int x,int l,int r) { if(l==r) { mx[x]=sum[x]=a[l];mc[x]=1;se[x]=-1; return; } int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); pu(x); } void modify(int x,int l,int r,int s,int t,int v) { if(v>=mx[x]) return; if(s<=l && r<=t && v>se[x]) { dec(x,v);return; } pd(x); int mid=(l+r)>>1; if(s<=mid) modify(x<<1,l,mid,s,t,v); if(mid<t) modify(x<<1|1,mid+1,r,s,t,v); pu(x); } LL qsum(int x,int l,int r,int s,int t) { if(s<=l && r<=t) return sum[x]; pd(x); int mid=(l+r)>>1;LL res=0; if(s<=mid) res+=qsum(x<<1,l,mid,s,t); if(mid<t) res+=qsum(x<<1|1,mid+1,r,s,t); return res; } int qmax(int x,int l,int r,int s,int t) { if(s<=l && r<=t) return mx[x]; pd(x); int mid=(l+r)>>1,res=0; if(s<=mid) res=max(res,qmax(x<<1,l,mid,s,t)); if(mid<t) res=max(res,qmax(x<<1|1,mid+1,r,s,t)); return res; } void solve() { int n,m,opt,s,t,x; read(n);read(m); REP(i,1,n) read(a[i]); build(1,1,n); REP(i,1,m) { read(opt);read(s);read(t); if(opt==0) { read(x); modify(1,1,n,s,t,x); } else if(opt==1) printf("%d\n",qmax(1,1,n,s,t)); else printf("%lld\n",qsum(1,1,n,s,t)); } } int main() { int T; read(T); while(T--) solve(); return 0; } |