SPOJ-GSS系列

数据结构好题啊。。。

GSS1 - Can you answer these queries I

链接

题意：维护区间内最大子段和

直接线段树。。。

GSS4 - Can you answer these queries IV

链接

题意：维护区间开方，区间求和。区间内的数不超过1e18。

用计算器可知，1e18开方6次后即可变成1。维护线段树，每个数最多改6次，每次时间复杂度为(O(log n))，总时间复杂度为(O(n log n))。

三倍经验：luogu bzoj

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long ll;
const int Maxn=410000;

int tl[Maxn],tr[Maxn],n,opt,l,r;
int bj[Maxn];
ll tn[Maxn],a[Maxn];

inline void update(int root) {
	tn[root]=tn[root<<1]+tn[(root<<1)|1];
	bj[root]=bj[root<<1]&bj[(root<<1)|1];
}

void build(int root,int l,int r) {
	tl[root]=l;
	tr[root]=r;
	if(l==r) {
		tn[root]=a[l];
		if(tn[root]<=1) bj[root]=1;
		return ;
	}
	int mid=l+r>>1;
	build(root<<1,l,mid);
	build((root<<1)|1,mid+1,r);
	update(root);
}

ll query(int root,int l,int r) {
	int lc=tl[root],rc=tr[root];
	int mid=lc+rc>>1;
	if(l<=lc&&r>=rc) return tn[root];
	ll ans=0;
	if(l<=mid) ans+=query(root<<1,l,r);
	if(r>mid) ans+=query((root<<1)|1,l,r);
	return ans;
}

void change(int root,int l,int r) {
	if(bj[root]) return ;
	int lc=tl[root],rc=tr[root];
	if(lc==rc) {
		tn[root]=sqrt(tn[root]);
		if(tn[root]<=1) bj[root]=1;
		return ;
	}
	int mid=lc+rc>>1;
	if(l<=mid) change(root<<1,l,r);
	if(r>mid) change((root<<1)|1,l,r);
	update(root);
}

int main() {
	int t=0;
	while(scanf("%d",&n)!=EOF) {
		t++;
		memset(bj,0,sizeof(bj));
		printf("Case #%d:
",t);
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		build(1,1,n);
		scanf("%d",&n);
		for(int i=1;i<=n;i++) {
			scanf("%d%d%d",&opt,&l,&r);
			if(l>r) swap(l,r);
			if(opt==1) printf("%lld
",query(1,l,r));
			else change(1,l,r);
		}
		putchar('
');
	}
	return 0;
}