Description

Input

Output

Data Constraint

Solution

• 吉如一论文里的线段树算法……

• 对于一个区间，记录三个值：最大值 mx1，最大值的个数 cnt，严格次大值 mx2。

• 那么在一个区间内要修改为 x ，

• 如果有 x≥mx1 ，就不用修改，直接退出。

• 如果有 mx2≤x<mx1 ，则区间和 sum−=(mx1−x)∗cnt ，再 mx1=x 即可。

• 如果 x<mx2 ，则直接递归左右子树。

• 记得下传标记，要随时维护严格次大值。

• 时间复杂度通过势能分析可得为 O(N log N) 。

Code

#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int N=5e5+5; struct data {int mx1,cnt,mx2;LL sum; }f[N<<2]; LL last; int qx,qy,qz; int a[N]; template<typename T>inline T read() {T X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int max(int x,int y) {return x>y?x:y; } inline void update(int v) {int ls=v<<1,rs=ls|1;if(f[ls].mx1>f[rs].mx1){f[v].mx1=f[ls].mx1;f[v].cnt=f[ls].cnt;f[v].mx2=max(f[ls].mx2,f[rs].mx1);}elseif(f[ls].mx1<f[rs].mx1){f[v].mx1=f[rs].mx1;f[v].cnt=f[rs].cnt;f[v].mx2=max(f[rs].mx2,f[ls].mx1);}else{f[v].mx1=f[ls].mx1;f[v].cnt=f[ls].cnt+f[rs].cnt;f[v].mx2=max(f[ls].mx2,f[rs].mx2);}f[v].sum=f[ls].sum+f[rs].sum; } inline void modify(int v,int x) {if(x>=f[v].mx1) return;f[v].sum-=(LL)(f[v].mx1-x)*f[v].cnt;f[v].mx1=x; } inline void down(int v) {modify(v<<1,f[v].mx1);modify(v<<1|1,f[v].mx1); } void make(int v,int l,int r) {if(l==r){f[v].sum=f[v].mx1=a[l];f[v].cnt=1,f[v].mx2=-1;return;}int mid=l+r>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r);update(v); } void change(int v,int l,int r) {if(qz>=f[v].mx1) return;if(qx<=l && r<=qy && qz>f[v].mx2){modify(v,qz);return;}down(v);int mid=l+r>>1;if(qx<=mid) change(v<<1,l,mid);if(qy>mid) change(v<<1|1,mid+1,r);update(v); } LL find(int v,int l,int r) {if(qx<=l && r<=qy) return f[v].sum;int mid=l+r>>1;down(v);LL s=0;if(qx<=mid) s+=find(v<<1,l,mid);if(qy>mid) s+=find(v<<1|1,mid+1,r);update(v);return s; } int main() {int n=read<int>(),m=read<int>();for(int i=1;i<=n;i++) a[i]=read<int>();make(1,1,n);while(m--){int op=read<int>();qx=read<LL>()^last;qy=read<LL>()^last;if(op==1){int x=qy;qy=qx;int num=find(1,1,n);qz=max(num-x,0);change(1,1,n);}elseif(op==2){qz=read<LL>()^last;change(1,1,n);}else printf("%lld\n",last=find(1,1,n));}return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 5618. 【NOI2018模拟3.31】华胥梦天的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。