C++14(g++5.4) 解法, 执行用时: 521ms, 内存消耗: 64344K, 提交时间: 2018-11-17 14:47:42
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define pi 3.141592653589793
#define mod 998244353
#define LL long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sf(x) scanf("%lld",&x)
#define sc(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
using namespace std;
const int N = 300010;
LL f[N],d[N],mx1[N],mx2[N],n,m;
typedef pair<LL,int> P;
struct ST1
{
#define ls i<<1
#define rs i<<1|1
struct node
{
int lpos,rpos,l,r;
LL max;
} T[N<<2];
inline void push_up(int i)
{
T[i].max=max(T[ls].max,T[rs].max);
T[i].lpos=T[T[ls].max>=T[rs].max?ls:rs].lpos;
T[i].rpos=T[T[rs].max>=T[ls].max?rs:ls].rpos;
}
void build(int i,int l,int r)
{
T[i]=node{0,0,l,r,0};
if (l==r)
{
T[i].lpos=T[i].rpos=l;
T[i].max=d[l]; return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
push_up(i);
}
void update(int i,int pos,LL x)
{
if (T[i].l==T[i].r)
{
T[i].max+=x;
return;
}
int mid=(T[i].l+T[i].r)>>1;
if (mid>=pos) update(ls,pos,x);
else if (mid<pos) update(rs,pos,x);
push_up(i);
}
int query1(int i,int l,int r,LL x)
{
if (l>r||T[i].max<x) return 0;
if (T[i].l==T[i].r) return T[i].max>=x?T[i].l:0;
int mid=(T[i].l+T[i].r)>>1,res=0;
if (l<=mid) res=query1(ls,l,r,x);
if (r>mid&&!res) res=query1(rs,l,r,x);
return res;
}
int query2(int i,int l,int r,LL x)
{
if (l>r||T[i].max<x) return 0;
if (T[i].l==T[i].r) return T[i].max>=x?T[i].l:0;
int mid=(T[i].l+T[i].r)>>1,res=0;
if (r>mid&&!res) res=query2(rs,l,r,x);
if (l<=mid&&!res) res=query2(ls,l,r,x);
return res;
}
P getmax1(int i,int l,int r)
{
if (l<=T[i].l&&T[i].r<=r) return P(T[i].max,T[i].lpos);
int mid=(T[i].l+T[i].r)>>1; P res={0,0};
if (l<=mid) res=getmax1(ls,l,r);
if (r>mid)
{
P tmp=getmax1(rs,l,r);
if (tmp.first>res.first) res=tmp;
}
return res;
}
P getmax2(int i,int l,int r)
{
if (l<=T[i].l&&T[i].r<=r) return P(T[i].max,T[i].rpos);
int mid=(T[i].l+T[i].r)>>1; P res={0,0};
if (r>mid) res=getmax2(rs,l,r);
if (l<=mid)
{
P tmp=getmax2(ls,l,r);
if (tmp.first>res.first) res=tmp;
}
return res;
}
} seg1;
struct ST2
{
#define ls i<<1
#define rs i<<1|1
struct node
{
LL lazy,sum;
int l,r;
} T[N<<2];
void build(int i,int l,int r)
{
T[i]=node{0,0,l,r};
if (l==r)
{
T[i].sum=f[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
T[i].sum=T[ls].sum+T[rs].sum;
}
inline void push_down(int i)
{
LL lazy=T[i].lazy;
T[ls].lazy=lazy; T[rs].lazy=lazy;
T[ls].sum=(T[ls].r-T[ls].l+1)*lazy;
T[rs].sum=(T[rs].r-T[rs].l+1)*lazy;
T[i].lazy=0;
}
void update(int i,int l,int r,LL x)
{
if (l>r) return;
if (T[i].l==l&&T[i].r==r)
{
T[i].sum=(T[i].r-T[i].l+1)*x;
T[i].lazy=x; return;
}
if (T[i].lazy) push_down(i);
int mid=(T[i].l+T[i].r)>>1;
if (mid>=r) update(ls,l,r,x);
else if (mid<l) update(rs,l,r,x);
else
{
update(ls,l,mid,x);
update(rs,mid+1,r,x);
}
T[i].sum=T[ls].sum+T[rs].sum;
}
} seg2;
int main()
{
sf(n); sf(m);
for(int i=1;i<=n;i++) sf(d[i]);
seg1.build(1,1,n);
for(int i=1;i<=n;i++)
mx1[i]=max(mx1[i-1],d[i]);
for(int i=n;i>=1;i--)
mx2[i]=max(mx2[i+1],d[i]);
for(int i=1;i<=n;i++)
f[i]=max(d[i],min(mx1[i-1],mx2[i+1]));
seg2.build(1,1,n);
while(m--)
{
LL op,l,r,v;
sf(op);
if (op==1) printf("%lld\n",seg2.T[1].sum);
else if (op==2)
{
sc(l,r,v);
int ll=seg1.query1(1,1,l-1,v);
int rr=seg1.query2(1,r+1,n,v);
if (ll) ll=l; else ll=seg1.query1(1,l,r,v);
if (rr) rr=r; else rr=seg1.query2(1,l,r,v);
if (ll*rr==0) puts("0"); else printf("%d\n",rr-ll+1);
} else
{
sf(l); sf(v);
seg1.update(1,l,v); d[l]+=v;
int ll=seg1.query2(1,1,l-1,d[l]);
int rr=seg1.query1(1,l+1,n,d[l]);
if (ll&&rr) continue;
seg2.update(1,l,l,d[l]);
if (ll) seg2.update(1,ll+1,l-1,d[l]);
else if (l!=1)
{
P tmp=seg1.getmax2(1,1,l-1);
seg2.update(1,tmp.second,l-1,tmp.first);
}
if (rr) seg2.update(1,l+1,rr-1,d[l]);
else if (l!=1)
{
P tmp=seg1.getmax1(1,l+1,n);
seg2.update(1,l+1,tmp.second,tmp.first);
}
}
}
return 0;
}
/*
5 100
1 2 3 4 5
2 1 5 4
3 2 4
3 4 2
1
2 1 5 6
3 1 3
1
*/
C++11(clang++ 3.9) 解法, 执行用时: 1091ms, 内存消耗: 59232K, 提交时间: 2018-11-16 21:14:20
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
typedef long long ll;
typedef pair<int,int> pii;
inline int read() {
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int maxn=300010;
struct Segment {
ll maxv[maxn<<2],sumv[maxn<<2],setv[maxn<<2];
void update(int o,int l,int r,int ql,int qr,ll val) {
if(ql<=l&&r<=qr) {setv[o]=maxv[o]=val;sumv[o]=val*(r-l+1);return;}
int mid=l+r>>1,lc=o<<1,rc=lc|1;
if(setv[o]>=0) {
setv[lc]=setv[rc]=maxv[lc]=maxv[rc]=setv[o];
sumv[lc]=setv[o]*(mid-l+1);sumv[rc]=setv[o]*(r-mid);
setv[o]=-1;
}
if(ql<=mid) update(lc,l,mid,ql,qr,val);
if(qr>mid) update(rc,mid+1,r,ql,qr,val);
maxv[o]=max(maxv[lc],maxv[rc]);
sumv[o]=sumv[lc]+sumv[rc];
}
ll getsum(int o,int l,int r,int ql,int qr) {
if(!qr) return 0;
if(ql<=l&&r<=qr) return sumv[o];
if(setv[o]>=0) return setv[o]*(min(r,qr)-max(l,ql)+1);
ll res=0;
int mid=l+r>>1,lc=o<<1,rc=lc|1;
if(ql<=mid) res+=getsum(lc,l,mid,ql,qr);
if(qr>mid) res+=getsum(rc,mid+1,r,ql,qr);
return res;
}
int find(int o,int l,int r,ll v) { //find the first position >=v
if(maxv[o]<v) return -1;
if(l==r) return l;
int mid=l+r>>1,lc=o<<1,rc=lc|1;
if(setv[o]>=0) {
setv[lc]=setv[rc]=maxv[lc]=maxv[rc]=setv[o];
sumv[lc]=setv[o]*(mid-l+1);sumv[rc]=setv[o]*(r-mid);
setv[o]=-1;
}
if(maxv[lc]>=v) return find(lc,l,mid,v);
return find(rc,mid+1,r,v);
}
}T,Tr;
int n,m,gap;
ll A[maxn],pre[maxn],suf[maxn],ans;
void work() {
rep(i,1,n) pre[i]=max(pre[i-1],A[i]);
dwn(i,n,1) suf[i]=max(suf[i+1],A[i]);
rep(i,1,n) if(pre[i-1]<suf[i+1]) gap=i;
rep(i,1,n) T.update(1,1,n,i,i,pre[i]);
dwn(i,n,1) Tr.update(1,1,n,n-i+1,n-i+1,suf[i]);
ans=0;
rep(i,1,gap) ans+=pre[i];
rep(i,gap+1,n) ans+=suf[i];
}
int qleft(int l,int r,ll v) {
if(l>r) return 0;
int p=T.find(1,1,n,v);if(p<0) return 0;
l=max(l,p);
return l<=r?r-l+1:0;
}
int qright(int l,int r,ll v) {
if(l>r) return 0;
int p=n-Tr.find(1,1,n,v)+1;if(p==n+2) return 0;
r=min(r,p);
return l<=r?r-l+1:0;
}
int main() {
// freopen("F.txt","r",stdin);
// freopen("F.out","w",stdout);
n=read();m=read();
rep(i,1,n) A[i]=read();work();
while(m--) {
int t=read(),x,v;
if(t==1) printf("%lld\n",ans);
else if(t==2) {
int l=read(),r=read(),v=read();
printf("%d\n",qleft(l,min(gap,r),v)+qright(max(gap+1,l),r,v));
}
else {
x=read(),v=read();A[x]+=v;
int p;
// premax
p=T.find(1,1,n,A[x]);if(p<0) p=n+1;
if(p>=x) T.update(1,1,n,x,p-1,A[x]);
// premin
p=n-Tr.find(1,1,n,A[x])+1;if(p==n+2) p=1;
if(p<=x) Tr.update(1,1,n,n-x+1,n-p,A[x]);
// rep(i,1,n) printf("%lld%c",T.getsum(1,1,n,i,i),i==n?'\n':' ');
// rep(i,1,n) printf("%lld%c",Tr.getsum(1,1,n,n-i+1,n-i+1),i==n?'\n':' ');
int l=1,r=n;
while(l<r) {
int mid=l+r>>1;
if(T.getsum(1,1,n,mid-1,mid-1)>Tr.getsum(1,1,n,n-mid,n-mid)) r=mid;
else l=mid+1;
}
gap=l-1;
// ans=0;
// rep(i,1,gap) ans+=T.getsum(1,1,n,i,i);
// rep(i,gap+1,n) ans+=Tr.getsum(1,1,n,n-i+1,n-i+1);
ans=T.getsum(1,1,n,1,gap)+Tr.getsum(1,1,n,1,n-gap);
// rep(i,1,n) printf("%lld%c",T.getsum(1,1,n,i,i),i==n?'\n':' ');
// rep(i,1,n) printf("%lld%c",Tr.getsum(1,1,n,n-i+1,n-i+1),i==n?'\n':' ');
// printf("%d %lld\n",gap,ans);
}
}
return 0;
}
。 
。