求助
查看原帖
求助
91736
RPChe_楼主2021/3/5 11:25

这份代码为什么在spoj上过不了编译啊QAQ

#include<bits/stdc++.h>
#define rep(i,a,b) for(R int i=a;i<=b;i++)
#define R register
#define endl putchar('\n')
const int maxn=500005;
const long long inf=0x3f3f3f3f3f3f3f3f;
#define int long long
using namespace std;

struct question {
	int l,r,num;
	bool operator < (const question &x) const {return r<x.r;}
}q[maxn];
int n,m,a[maxn],next[maxn],ans[maxn],seq[maxn],tot,head[maxn];

struct segment_tree {
	struct node {
		int mx,hmx,ad,had;
		#define hmx(x) nod[x].hmx
		#define mx(x) nod[x].mx
		#define ad(x) nod[x].ad
		#define had(x) nod[x].had
	}nod[maxn];
	#define ls (k<<1)
	#define rs (k<<1|1)
	#define mid ((l+r)>>1)
	
	void update(int k,int ad,int had) {
		had(k)=max(had(k),ad(k)+had);
		hmx(k)=max(hmx(k),mx(k)+had);
		ad(k)+=ad,mx(k)+=ad;
	}
	void pushdown(int k) {
		update(ls,ad(k),had(k)),update(rs,ad(k),had(k));
		ad(k)=had(k)=0;
	}
	void pushup(int k) {
		hmx(k)=max(hmx(ls),hmx(rs));
		mx(k)=max(mx(ls),mx(rs));
	}
	
	void add(int k,int l,int r,int x,int y,int v) {
		if(x<=l&&r<=y) return update(k,v,v);
		if(x<=mid) add(ls,l,mid,x,y,v);
		if(y>mid) add(rs,mid+1,r,x,y,v);
		pushup(k);
	}
	
	int query(int k,int l,int r,int x,int y) {
		if(x<=l&&r<=y) return hmx(k);
		int res=-inf;
		if(x<=mid) res=max(res,query(ls,l,mid,x,y));
		if(y>mid) res=max(res,query(rs,mid+1,r,x,y));
		return res;
	}
} smt;//吉老师线段树 

void solve() {
	sort(q+1,q+m+1);
	rep(i,1,m) {
		if(q[i].r!=q[i-1].r) rep(j,q[i-1].r+1,q[i].r) smt.add(1,1,n,next[j]+1,j,a[j]);
		ans[q[i].num]=smt.query(1,1,n,q[i].l,q[i].r);
	}
}

void init() {
	sort(seq+1,seq+tot+1);
	tot=unique(seq+1,seq+tot+1)-seq-1;//离散化 
	rep(i,1,n) {
		int nw=lower_bound(seq+1,seq+tot+1,a[i])-seq;
		next[i]=head[nw],head[nw]=i;
	}
}

signed main() {
	scanf("%lld",&n);
	rep(i,1,n) scanf("%lld",&a[i]),seq[++tot]=a[i];
	init();
	scanf("%lld",&m);
	rep(i,1,m) scanf("%lld%lld",&q[i].l,&q[i].r),q[i].num=i;
	solve();
	rep(i,1,m) printf("%lld\n",ans[i]);
	return 0;
}
2021/3/5 11:25
加载中...