线段树专辑

这几天陆陆续续更新了下边几道我所能找到得具有一些代表性的线段树题目
从最最简单的区间求和到对区间的各种操作都包涵在这些题目里了
相信对一些准备学习线段树的人有一定得帮助
突然发现自己对数据结构的题目非常有感觉,所以在刷下边的题的同时也生出灵感出了好几道线段树题目
等比赛结束后也会陆续加进里边

快半年过去代码风格也有很大的改变，感觉以前写的代码很不规范，用自己在预定义中定义的一些函数，但后来感觉作用不是很大，所以又删去了，所以现在看代码可能找不到以前我定义的一些函数，本来想更新一下的，无奈这些函数用的太多，改之太过麻烦，所以在此处申明一下
#define LL(x) ((x)<<1)
#define RR(x) ((x)<<1|1)
#define FF(i,n) for(int i = 0 ; i < n ; i ++)
若还有不清楚的地方，只管提出来便是，我一定一一改正

1.hdu1166 敌兵布阵
更新节点,区间求和

^?View Code CPP

struct Seg_Tree{
	int left,right,num;
	int calmid() {
		return (left+right)/2;
	}
}tt[150000];
int num[50001];
int build(int left,int right,int idx) {
	tt[idx].left = left;
	tt[idx].right = right;
	if(left == right) {
		return tt[idx].num = num[left];
	}
	int mid = (left + right)/2;
	return tt[idx].num = build(left,mid,LL(idx)) + build(mid+1,right,RR(idx));
}
 
void update(int id,int x,int idx) {
	tt[idx].num += x;
	if(tt[idx].left == tt[idx].right) {
		return ;
	}
	int mid = tt[idx].calmid();
	if(id <= mid) {
		update(id,x,LL(idx));
	} else {
		update(id,x,RR(idx));
	}
}
 
int query(int left,int right,int idx) {
	if(left == tt[idx].left && right == tt[idx].right) {
		return tt[idx].num;
	}
	int mid = tt[idx].calmid();
	if(right <= mid) {
		return query(left,right,LL(idx));
	} else if(mid < left) {
		return query(left,right,RR(idx));
	} else {
		return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
	}
}
 
int main() {
	int T;
	scanf(“%d”,T);
	FF(cas,T) {
		int n;
		scanf(“%d”,&n);
		FOR(i,1,1+n) {
			scanf(“%d”,num[i]);
		}
		build(1,n,1);
		printf("Case %d:\n",cas+1);
		char com[9];
		while(scanf("%s",com)) {
			if(strcmp(com,"End") == 0)	break;
			int a,b;
			scanf("%d%d",&a,&b);
			switch(com[0]) {
				case 'Q':
					printf("%d\n",query(a,b,1));
					break;
				case 'A':
					update(a,b,1);
					break;
				case 'S':
					update(a,-b,1);
					break;
			}
		}
	}
	return 0;
}

.
2.hdu1754 I Hate It
更新节点,区间最值

^?View Code CPP

struct Seg_Tree {
	int left,right,val;
	int calmid() {
		return (left+right)/2;
	}
}tt[600000];
int val[200001];
 
int build(int left,int right,int idx) {
	tt[idx].left = left;
	tt[idx].right = right;
	if(left == right) {
		return tt[idx].val = val[left];
	}
	int mid = tt[idx].calmid();
	return tt[idx].val = max(build(left,mid,LL(idx)) , build(mid+1,right,RR(idx)));
}
 
void update(int id,int x,int idx) {
	if(tt[idx].left == tt[idx].right){
		tt[idx].val = x;
		return ;
	}
	int mid = tt[idx].calmid();
	if(id <= mid) {
		update(id,x,LL(idx));
	} else {
		update(id,x,RR(idx));
	}
	tt[idx].val = max(tt[LL(idx)].val , tt[RR(idx)].val);
}
 
int query(int left,int right,int idx) {
	if(left == tt[idx].left && right == tt[idx].right) {
		return tt[idx].val;
	}
	int mid = tt[idx].calmid();
	if(right <= mid) {
		return query(left,right,LL(idx));
	} else if(mid < left) {
		return query(left,right,RR(idx));
	} else {
		return max(query(left,mid,LL(idx)) , query(mid+1,right,RR(idx)));
	}
}
 
int main() {
	int n , m ;
	while(scanf("%d%d",&n,&m) == 2) {
		FOR(i,1,n+1) {
			scanf("%d",&val[i]);
		}
		build(1,n,1);
		while(m --) {
			char com[2];
			int a,b;
			scanf("%s%d%d",com,&a,&b);
			if(com[0] == 'Q') {
				printf("%d\n",query(a,b,1));
			} else {
				update(a,b,1);
			}
		}
	}
	return 0;
}

.
3.hdu1698 Just a Hook
成段更新,总区间求和

^?View Code CPP

int n;
struct Seg_Tree{
	int left,right,col;
}tt[300000];
 
void build(int left,int right,int idx) {
	tt[idx].left = left;
	tt[idx].right = right;
	tt[idx].col = 1;
	if(left == right)	return ;
	int mid = (left + right)/2;
	build(left,mid,LL(idx));
	build(mid+1,right,RR(idx));
}
 
void update(int left,int right,int col,int idx) {
	if(left <= tt[idx].left && right >= tt[idx].right) {
		tt[idx].col = col;
		return ;
	}
	if(tt[idx].col != -1) {
		tt[LL(idx)].col = tt[RR(idx)].col = tt[idx].col;
		tt[idx].col = -1;
	}
	int mid = (tt[idx].left + tt[idx].right)/2;
    if(left <= mid) update(left,right,col,LL(idx));
    if(mid < right)    update(left,right,col,RR(idx));
 
}
 
int query(int left,int right,int idx) {
	if(left == tt[idx].left && right == tt[idx].right) {
		if(tt[idx].col != -1) {
			return (right - left + 1) * tt[idx].col;
		} else {
			int mid = (tt[idx].left + tt[idx].right)/2;
			return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
		}
	}
	int mid = (tt[idx].left + tt[idx].right)/2;
	if(right <= mid) {
		return query(left,right,LL(idx));
	} else if(left > mid) {
		return query(left,right,RR(idx));
	} else {
		return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
	}
}
 
int main() {
	int T;
	scanf("%d",&T);
	FF(cas,T) {
		int n , m ;
		scanf("%d",&n);
		build(1,n,1);
		scanf("%d",&m);
		while(m --) {
			int left,right,col;
			scanf("%d%d%d",&left,&right,&col);
			update(left,right,col,1);
		}
		printf("Case %d: The total value of the hook is %d.\n",cas+1,query(1,n,1));
	}
	return 0;
}

.
4.hdu1394 Minimum Inversion Number
更新节点,区间求和(实现nlog(n)的逆序数方法,和树状数组比起来实在是有点鸡肋)

^?View Code CPP

struct Seg_Tree {
	int left,right,val;
	int calmid() {
		return (left+right)/2;
	}
}tt[15000];
int val[5001];
 
void build(int left,int right,int idx) {
	tt[idx].left = left;
	tt[idx].right = right;
	tt[idx].val = 0;
	if(left == right) {
		return ;
	}
	int mid = tt[idx].calmid();
	build(left,mid,LL(idx));
	build(mid+1,right,RR(idx));
}
 
int query(int left,int right,int idx) {
	if(left == tt[idx].left && right == tt[idx].right) {
		return tt[idx].val;
	}
	int mid = tt[idx].calmid();
	if(right <= mid) {
		return query(left,right,LL(idx));
	} else if(mid < left) {
		return query(left,right,RR(idx));
	} else {
		return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
	}
}
 
void update(int id,int idx) {
	tt[idx].val ++;
	if(tt[idx].left == tt[idx].right) {
		return ;
	}
	int mid = tt[idx].calmid();
	if(id <= mid) {
		update(id,LL(idx));
	} else {
		update(id,RR(idx));
	}
}
 
int main() {
	int n;
	while(scanf("%d",&n) == 1) {
		build(0,n-1,1);
		int sum = 0;
		FF(i,n) {
			scanf(“%d”,&val[i]);
			sum += query(val[i],n-1,1);
			update(val[i],1);
		}
		int ret = sum;
		FF(i,n) {
			sum = sum - val[i] + (n - val[i] - 1);
			checkmin(ret,sum);
		}
		printf("%d\n",ret);
	}
	return 0;
}

.
5.hdu1779 9-Problem C暂不公开
成段更新,区间最值

^?View Code CPP

struct Node{
	int idx;
	int val;
	friend bool operator < (Node a,Node b) {
		if(a.val == b.val) {
			return a.idx > b.idx;
		}
		return a.val < b.val;
	}
};
struct Seg_Tree {
	int left,right;
	Node node;
	int add;
	int calmid() {
		return (left+right)/2;
	}
}tt[300000];
 
void build(int left,int right,int idx) {
	tt[idx].left = left;
	tt[idx].right = right;
	tt[idx].add = 0;
	tt[idx].node.idx = left;
	tt[idx].node.val = 0;
	if(left == right) {
		return ;
	}
	int mid = tt[idx].calmid();
	build(left,mid,LL(idx));
	build(mid+1,right,RR(idx));
}
 
void update(int left,int right,int add,int idx) {
	if(left <= tt[idx].left && right >= tt[idx].right) {
		tt[idx].node.val += add;
		tt[idx].add += add;
		return ;
	}
	if(tt[idx].add) {
		tt[LL(idx)].node.val += tt[idx].add;
		tt[RR(idx)].node.val += tt[idx].add;
		tt[LL(idx)].add += tt[idx].add;
		tt[RR(idx)].add += tt[idx].add;
		tt[idx].add = 0;
	}
	int mid = tt[idx].calmid();
	if(left <= mid) update(left,right,add,LL(idx));
	if(mid < right) update(left,right,add,RR(idx));
	tt[idx].node = max(tt[LL(idx)].node , tt[RR(idx)].node);
}
 
Node query(int left,int right,int idx) {
	if(left == tt[idx].left && right == tt[idx].right) {
		return tt[idx].node;
	}
	if(tt[idx].add) {
		tt[LL(idx)].node.val += tt[idx].add;
		tt[RR(idx)].node.val += tt[idx].add;
		tt[LL(idx)].add += tt[idx].add;
		tt[RR(idx)].add += tt[idx].add;
		tt[idx].add = 0;
	}
	int mid = tt[idx].calmid();
	if(right <= mid) {
		return query(left,right,LL(idx));
	} else if(left > mid) {
		return query(left,right,RR(idx));
	} else {
		return max(query(left,mid,LL(idx)) , query(mid+1,right,RR(idx)));
	}
}
 
int main() {
	int n , m ;
	while(scanf("%d%d",&n,&m) == 2) {
		if(n == 0 && m == 0)	break;
		build(1,n,1);
		while(m --) {
			char com[2];
			scanf("%s",&com);
			if(com[0] == 'I') {
				int a,b,c;
				scanf("%d%d%d",&a,&b,&c);
				update(a,b,c,1);
			} else {
				int a,b;
				scanf("%d%d",&a,&b);
				Node ret = query(a,b,1);
				printf("%d\n",ret.val);
				update(ret.idx,ret.idx,-ret.val,1);
			}
		}
	}
	return 0;
}

.
6.pku2777 Count Color
成段更新,区间统计,位运算加速(我总把query里的传递给子节点的步骤忘了)

^?View Code CPP

template<class T> inline T countbit(T n)	{return n?1+countbit(n&(n-1)):0;}
#define two(x)				((LL)1<<(x))
struct Seg_Tree{
	int left,right;
	int col;
	bool cover;
	int calmid() {
		return (left+right)/2;
	}
}tt[300000];
 
void build(int left,int right,int idx) {
	tt[idx].left = left;
	tt[idx].right = right;
	tt[idx].col = two(1);
	tt[idx].cover = true;
	if(left == right) {
		return ;
	}
	int mid = tt[idx].calmid();
	build(left,mid,LL(idx));
	build(mid+1,right,RR(idx));
}
 
void update(int left,int right,int c,int idx) {
	if(left <= tt[idx].left && right >= tt[idx].right) {
		tt[idx].cover = true;
		tt[idx].col = two(c);
		return ;
	}
	if(tt[idx].cover) {
		tt[RR(idx)].col = tt[LL(idx)].col = tt[idx].col;
		tt[RR(idx)].cover = tt[LL(idx)].cover = true;
		tt[idx].cover = false;
	}
	int mid = tt[idx].calmid();
	if(left <= mid) update(left,right,c,LL(idx));
	if(mid < right) update(left,right,c,RR(idx));
	tt[idx].col = tt[LL(idx)].col | tt[RR(idx)].col;
}
 
int query(int left,int right,int idx) {
	if(left == tt[idx].left && right == tt[idx].right) {
		return tt[idx].col;
	}
	if(tt[idx].cover) {
		tt[RR(idx)].col = tt[LL(idx)].col = tt[idx].col;
		tt[RR(idx)].cover = tt[LL(idx)].cover = true;
		tt[idx].cover = false;
	}
	int mid = tt[idx].calmid();
	if(right <= mid) {
		return query(left,right,LL(idx));
	} else if(mid < left) {
		return query(left,right,RR(idx));
	} else {
		return query(left,mid,LL(idx)) | query(mid+1,right,RR(idx));
	}
}
 
int main() {
	int n,T,o;
	while(scanf("%d%d%d",&n,&T,&o) == 3) {
		build(1,n,1);
		while(o--) {
			char ch[2];
			scanf("%s",&ch);
			if(ch[0] == 'C') {
				int a,b,c;
				scanf("%d%d%d",&a,&b,&c);
				if(a > b)	swap(a,b);
				update(a,b,c,1);
			} else {
				int a,b;
				scanf("%d%d",&a,&b);
				if(a > b)	swap(a,b);
				printf("%d\n",countbit(query(a,b,1)));
			}
		}
	}
	return 0;
}

.
7.pku3468 A Simple Problem with Integers
成段更新,区间求和(中间乘法会超int..纠结了)

^?View Code CPP

struct Seg_Tree{
	int left,right;
	LL sum;
	int add;
	int calmid() {
		return (left+right)/2;
	}
	int caldis() {
		return right - left + 1;
	}
}tt[400000];
 
int val[100001];
 
LL build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].add = 0;
	if(l == r) {
		return tt[idx].sum = val[l];
	}
	int mid = tt[idx].calmid();
	return tt[idx].sum = build(l,mid,LL(idx)) + build(mid+1,r,RR(idx));
}
 
void update(int l,int r,int add,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		tt[idx].add += add;
		tt[idx].sum += (LL)tt[idx].caldis() * add;
		return ;
	}
	if(tt[idx].add) {
		tt[LL(idx)].sum += (LL)tt[LL(idx)].caldis() * tt[idx].add;
		tt[RR(idx)].sum += (LL)tt[RR(idx)].caldis() * tt[idx].add;
		tt[LL(idx)].add += tt[idx].add;
		tt[RR(idx)].add += tt[idx].add;
		tt[idx].add = 0;
	}
	int mid = tt[idx].calmid();
	if(l <= mid) update(l,r,add,LL(idx));
	if(mid < r)	update(l,r,add,RR(idx));
	tt[idx].sum = tt[LL(idx)].sum + tt[RR(idx)].sum;
}
 
LL query(int l,int r,int idx) {
	if(l == tt[idx].left && r == tt[idx].right) {
		return tt[idx].sum;
	}
	if(tt[idx].add) {
		tt[LL(idx)].sum += (LL)tt[LL(idx)].caldis() * tt[idx].add;
		tt[RR(idx)].sum += (LL)tt[RR(idx)].caldis() * tt[idx].add;
		tt[LL(idx)].add += tt[idx].add;
		tt[RR(idx)].add += tt[idx].add;
		tt[idx].add = 0;
	}
	int mid = tt[idx].calmid();
	if(r <= mid) {
		return query(l,r,LL(idx));
	} else if(mid < l) {
		return query(l,r,RR(idx));
	} else {
		return query(l,mid,LL(idx)) + query(mid+1,r,RR(idx));
	}
}
 
int main() {
	int n , m ;
	while(scanf("%d%d",&n,&m) == 2) {
		FOR(i,1,n+1) {
			scanf("%d",&val[i]);
		}
		build(1,n,1);
		while(m --) {
			char com[2];
			scanf("%s",com);
			if(com[0] == 'Q') {
				int a,b;
				scanf("%d%d",&a,&b);
				printf("%lld\n",query(a,b,1));
			} else {
				int a,b,c;
				scanf("%d%d%d",&a,&b,&c);
				update(a,b,c,1);
			}
		}
	}
	return 0;
}

.
8.pku2528 Mayor’s posters
成段更新,区间统计(离散化)

^?View Code CPP

struct Seg_Tree{
	int left;
	int right;
	int col;
	int mid() {
		return (left+right)>>1;
	}
}tt[66666];
 
struct H{
	int left,right;
}hh[10001];
int pos[20001];
bool hash[10001];
int n , m ,ans ;
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].col = -1;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int l,int r,int col,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		tt[idx].col = col;
		return ;
	}
	if(tt[idx].col != -1) {
		tt[LL(idx)].col = tt[RR(idx)].col = tt[idx].col;
		tt[idx].col = -1;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,col,LL(idx));
	if(mid < r)	update(l,r,col,RR(idx));
}
 
void query(int l,int r,int idx) {
	if(tt[idx].col != -1) {
		if(!hash[tt[idx].col]) {
			ans ++;
			hash[tt[idx].col] = true;
		}
		return ;
	}
	int mid = tt[idx].mid();
	if(r <= mid) {
		query(l,r,LL(idx));
	} else if(mid < l) {
		query(l,r,RR(idx));
	} else {
		query(l,mid,LL(idx));
		query(mid+1,r,RR(idx));
	}
}
 
int Bin(int x) {
	int lo = 0;
	int hi = m-1;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(pos[mid] == x) {
			return mid;
		}
		if(pos[mid] < x) {
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return -1;
}
 
int main() {
	int T;
	scanf("%d",&T);
	while(T --) {
		scanf("%d",&n);
		FF(i,n) {
			scanf("%d%d",&hh[i].left,&hh[i].right);
			pos[LL(i)] = hh[i].left;
			pos[RR(i)] = hh[i].right;
		}
		sort(pos,pos+2*n);
		m = 0;
		FF(i,2*n) {
			if(i == 0 || pos[i] != pos[i-1]) {
				pos[m++] = pos[i];
			}
		}
		build(0,m-1,1);
		FF(i,n) {
			update(Bin(hh[i].left),Bin(hh[i].right),i,1);
		}
		ans = 0;
		CC(hash,false);
		query(0,m-1,1);
		printf("%d\n",ans);
	}
	return 0;
}

.
9.hdu2795 Billboard
更新节点,询问特殊(暑假的时候不会线段树被这水题狂虐)

^?View Code CPP

struct Node {
	int val;
	int idx;
	friend bool operator < (Node a , Node b) {
		if(a.val == b.val) {
			return a.idx > b.idx;
		}
		return a.val < b.val;
	}
}error;
 
struct Seg_Tree{
	int left,right;
	Node node;
	int mid() {
		return (left + right)>>1;
	}
}tt[800000];
 
int n , h , m;
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].node.idx = l;
	tt[idx].node.val = h;
	if(l == r) return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int l,int r,int val,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		tt[idx].node.val += val;
		return ;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,val,LL(idx));
	if(mid < r)	update(l,r,val,RR(idx));
	tt[idx].node = max(tt[LL(idx)].node,tt[RR(idx)].node);
}
 
Node query(int w,int idx) {
	if(tt[idx].node.val < w) {
		return error;
	}
	if(tt[idx].left == tt[idx].right) {
		return tt[idx].node;
	}
	if(tt[LL(idx)].node.val >= w) {
		return query(w,LL(idx));
	} else {
		return query(w,RR(idx));
	}
}
 
int main() {
	error.idx = -1;
	while(scanf("%d%d%d",&n,&h,&m) == 3) {
		checkmin(n,m);
		build(1,n,1);
		while(m --) {
			int w;
			scanf("%d",&w);
			Node ret = query(w,1);
			printf("%d\n",ret.idx);
			if(ret.idx != -1) {
				update(ret.idx,ret.idx,-w,1);
			}
		}
	}
	return 0;
}

.
10.pku3667 Hotel
成段更新,寻找空间(经典类型,求一块满足条件的最左边的空间)

^?View Code CPP

struct Seg_Tree{
	int left,right;
	int cval,lval,rval;
	int st;
	int mid() {
		return (left+right)>>1;
	}
	void doit() {
		cval = lval = rval = st ? 0 : dis();
	}
	int dis() {
		return (right - left + 1);
	}
}tt[150000];
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].st = -1;
	tt[idx].cval = tt[idx].lval = tt[idx].rval = tt[idx].dis();
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int l,int r,int st,int idx) {
	if(tt[idx].left >= l && r >= tt[idx].right) {
		tt[idx].st = st;
		tt[idx].doit();
		return ;
	}
	if(tt[idx].st != -1) {
		tt[LL(idx)].st = tt[RR(idx)].st = tt[idx].st;
		tt[LL(idx)].doit();
		tt[RR(idx)].doit();
		tt[idx].st = -1;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,st,LL(idx));
	if(mid < r)	update(l,r,st,RR(idx));
 
	tt[idx].cval = max( tt[LL(idx)].rval + tt[RR(idx)].lval , max(tt[LL(idx)].cval,tt[RR(idx)].cval) );
	tt[idx].lval = tt[LL(idx)].lval;
	tt[idx].rval = tt[RR(idx)].rval;
	if(tt[LL(idx)].cval == tt[LL(idx)].dis()) {
		tt[idx].lval += tt[RR(idx)].lval;
	}
	if(tt[RR(idx)].cval == tt[RR(idx)].dis()) {
		tt[idx].rval += tt[LL(idx)].rval;
	}
}
 
int query(int w,int idx) {
	if(tt[idx].left == tt[idx].right && w == 1) {
		return tt[idx].left;
	}
	if(tt[idx].st != -1) {
		tt[LL(idx)].st = tt[RR(idx)].st = tt[idx].st;
		tt[LL(idx)].doit();
		tt[RR(idx)].doit();
		tt[idx].st = -1;
	}
	if(tt[LL(idx)].cval >= w) {
		return query(w,LL(idx));
	} else if(tt[LL(idx)].rval + tt[RR(idx)].lval >= w) {
		return tt[LL(idx)].right - tt[LL(idx)].rval + 1;
	} else if(tt[RR(idx)].cval >= w){
		return query(w,RR(idx));
	} else {
		return 0;
	}
}
 
int main() {
	int n , m;
	while(scanf("%d%d",&n,&m) == 2) {
		build(1,n,1);
		while(m --) {
			int com;
			scanf("%d",&com);
			if(com == 1) {
				int a;
				scanf("%d",&a);
				int s = query(a,1);
				printf("%d\n",s);
				if(s) {
					update(s,s+a-1,1,1);
				}
			} else {
				int a,b;
				scanf("%d%d",&a,&b);
				update(a,a+b-1,0,1);
			}
		}
	}
	return 0;
}

.
11.hdu1540 Tunnel Warfare
更新节点,询问节点所在区间(同上一道Hotel一样类型的题目)

^?View Code CPP

struct Seg_Tree{
	int left,right;
	int cval,lval,rval;
	int mid() {
		return (left+right)>>1;
	}
	void doit(int st) {
		cval = lval = rval = st ? 0 : dis();
	}
	int dis() {
		return (right - left + 1);
	}
}tt[150000];
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].cval = tt[idx].lval = tt[idx].rval = tt[idx].dis();
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int id,int st,int idx) {
	if(tt[idx].left == tt[idx].right) {
		tt[idx].doit(st);
		return ;
	}
	int mid = tt[idx].mid();
	if(id <= mid) {
		update(id,st,LL(idx));
	} else {
		update(id,st,RR(idx));
	}
	int l = LL(idx);
	int r = RR(idx);
	tt[idx].cval = max(tt[l].rval + tt[r].lval , max(tt[l].cval , tt[r].cval));
	tt[idx].lval = tt[l].lval;
	tt[idx].rval = tt[r].rval;
	if(tt[l].cval == tt[l].dis()) {
		tt[idx].lval += tt[r].lval;
	}
	if(tt[r].cval == tt[r].dis()) {
		tt[idx].rval += tt[l].rval;
	}
}
 
int query(int id,int idx) {
	if(tt[idx].left == tt[idx].right || tt[idx].cval == 0 || tt[idx].cval == tt[idx].dis()) {
		return tt[idx].cval;
	}
	int mid = tt[idx].mid();
	if(id <= mid) {
		if(id > tt[LL(idx)].right - tt[LL(idx)].rval) {
			return query(id,LL(idx)) + query(tt[RR(idx)].left,RR(idx));
		} else {
			return query(id,LL(idx));
		}
	} else {
		if(id < tt[RR(idx)].left + tt[RR(idx)].lval) {
			return query(tt[LL(idx)].right,LL(idx)) + query(id,RR(idx));
		} else {
			return query(id,RR(idx));
		}
	}
}
 
stack <int> ss;
int main() {
	int n , m ;
	while(scanf("%d%d",&n,&m) == 2) {
		build(1,n,1);
		while(m --) {
			char com[2];
			scanf("%s",com);
			if(com[0] == 'D') {
				int idx;
				scanf("%d",&idx);
				ss.push(idx);
				update(idx,1,1);
			} else if(com[0] == 'Q') {
				int idx;
				scanf("%d",&idx);
				printf("%d\n",query(idx,1));
			} else {
				if(ss.empty())	continue;
				update(ss.top(),0,1);
				ss.pop();
			}
		}
	}
	return 0;
}

.
12.hdu2871 Memory Control
hotel变形题目,三个都函数一样(vector忘记清空检查了好久)

^?View Code CPP

struct Seg_Tree{
	int left,right;
	int cval,lval,rval;
	int st;
	int mid() {
		return (left+right)>>1;
	}
	void doit() {
		cval = lval = rval = st ? 0 : dis();
	}
	int dis() {
		return (right - left + 1);
	}
}tt[150000];
 
struct Block{
	int start;
	int end;
};
vector <Block> hh;
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].cval = tt[idx].lval = tt[idx].rval = tt[idx].dis();
	tt[idx].st = -1;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int l,int r,int st,int idx) {
	if(tt[idx].left >= l && r >= tt[idx].right) {
		tt[idx].st = st;
		tt[idx].doit();
		return ;
	}
	if(tt[idx].st != -1) {
		tt[LL(idx)].st = tt[RR(idx)].st = tt[idx].st;
		tt[LL(idx)].doit();
		tt[RR(idx)].doit();
		tt[idx].st = -1;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,st,LL(idx));
	if(mid < r)	update(l,r,st,RR(idx));
 
	tt[idx].cval = max( tt[LL(idx)].rval + tt[RR(idx)].lval , max(tt[LL(idx)].cval,tt[RR(idx)].cval) );
	tt[idx].lval = tt[LL(idx)].lval;
	tt[idx].rval = tt[RR(idx)].rval;
	if(tt[LL(idx)].cval == tt[LL(idx)].dis()) {
		tt[idx].lval += tt[RR(idx)].lval;
	}
	if(tt[RR(idx)].cval == tt[RR(idx)].dis()) {
		tt[idx].rval += tt[LL(idx)].rval;
	}
}
 
int query(int w,int idx) {
	if(tt[idx].left == tt[idx].right) {
		if(tt[idx].cval == w) {
			return tt[idx].left;
		} else {
			return 0;
		}
	}
	if(tt[idx].st != -1) {
		tt[LL(idx)].st = tt[RR(idx)].st = tt[idx].st;
		tt[LL(idx)].doit();
		tt[RR(idx)].doit();
		tt[idx].st = -1;
	}
	if(tt[LL(idx)].cval >= w) {
		return query(w,LL(idx));
	} else if(tt[LL(idx)].rval + tt[RR(idx)].lval >= w) {
		return tt[LL(idx)].right - tt[LL(idx)].rval + 1;
	} else if(tt[RR(idx)].cval >= w){
		return query(w,RR(idx));
	} else {
		return 0;
	}
}
 
int Bin(int x) {
	int lo = 0;
	int hi = sz(hh) - 1;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(hh[mid].start <= x) {
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return lo;
}
 
int main() {
	int n , m ;
	while(scanf("%d%d",&n,&m) == 2) {
		build(1,n,1);
		hh.clear();
		while(m --) {
			char com[9];
			scanf("%s",com);
			if(strcmp(com,"Reset") == 0) {
				update(1,n,0,1);
				hh.clear();
				puts("Reset Now");
			} else if(strcmp(com,"Free") == 0) {
				int idx;
				scanf("%d",&idx);
				int id = Bin(idx) - 1;
				if(id == -1 || hh[id].end < idx) {
					puts("Reject Free");
				} else {
					printf("Free from %d to %d\n",hh[id].start,hh[id].end);
					update(hh[id].start,hh[id].end,0,1);
					hh.erase(hh.begin()+id,hh.begin()+id+1);
				}
			} else if(strcmp(com,"New") == 0) {
				int w;
				scanf("%d",&w);
				if(tt[1].cval < w) {
					puts("Reject New");
				} else {
					Block buf;
					buf.start = query(w,1);
					buf.end = buf.start + w - 1;
					int idx = Bin(buf.start);
					hh.insert(hh.begin()+idx,buf);
					update(buf.start,buf.end,1,1);
					printf("New at %d\n",buf.start);
				}
			} else { 
				int idx;
				scanf("%d",&idx);
				idx --;
				if(idx >= sz(hh)) {
					puts("Reject Get");
				} else {
					printf("Get at %d\n",hh[idx].start);
				}
			}
		}
		puts("");
	}
	return 0;
}

.
13.hdu3016 Man Down
成段更新,单点查询(简单线段树+简单DP)

^?View Code CPP

#define mix -2
 
struct Seg_Tree{
	int left;
	int right;
	int id;
	int mid() {
		return (left + right)>>1;
	}
}tt[400000];
 
struct H{
	int left;
	int right;
	int xl,xr,val,h;
}hh[100001];
int n;
bool cmp(H a,H b) {
	return a.h < b.h;
}
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].id = -1;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int l,int r,int id,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		tt[idx].id = id;
		return ;
	}
	if(tt[idx].id != mix) {
		tt[LL(idx)].id = tt[RR(idx)].id = tt[idx].id;
		tt[idx].id = mix;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,id,LL(idx));
	if(mid < r)	update(l,r,id,RR(idx));
}
 
int query(int pos,int idx) {
	if(tt[idx].id != mix) {
		return tt[idx].id;
	}
	if(tt[idx].id != mix) {
		tt[LL(idx)].id = tt[RR(idx)].id = tt[idx].id;
		tt[idx].id = mix;
	}
	int mid = tt[idx].mid();
	if(pos <= mid) {
		return query(pos,LL(idx));
	} else {
		return query(pos,RR(idx));
	}
}
 
int dp[100001];
 
int main() {
	while(scanf("%d",&n) == 1) {
		FF(i,n) {
			scanf("%d%d%d%d",&hh[i].h,&hh[i].xl,&hh[i].xr,&hh[i].val);
		}
		sort(hh,hh+n,cmp);
		build(1,100000,1);
		FF(i,n) {
			hh[i].left = query(hh[i].xl,1);
			hh[i].right = query(hh[i].xr,1);
			update(hh[i].xl,hh[i].xr,i,1);
		}
		int ret = -1;
		CC(dp,-1);
		dp[n-1] = 100;
		FFD(i,n) {
			if(dp[i] == -1)	continue;
			if(hh[i].left == -1) {
				checkmax(ret,dp[i] + hh[i].val);
			} else {
				checkmax(dp[hh[i].left] , dp[i] + hh[i].val);
			}
			if(hh[i].right == -1) {
				checkmax(ret,dp[i] + hh[i].val);
			} else {
				checkmax(dp[hh[i].right] , dp[i] + hh[i].val);
			}
		}
		printf("%d\n",ret);
	}
	return 0;
}

.
14.hdu1542 Atlantis
矩形面积并,扫描线法(发现我们HDU的队员的矩形面积交模板基本都是在最坏情况下更新到底,宁波惨痛的教训啊..)

^?View Code CPP

struct Seg_Tree{
	int left,right;
	int cnt;
	double sum;
	int mid() {
		return (left + right) >> 1;
	}
}tt[6666];
struct Seg{
	double high;
	double left,right;
	int side;
}ss[2222];
bool cmp(Seg &a, Seg &b) {
	return a.high < b.high;
}
double pos[2222];
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].cnt = 0;
	tt[idx].sum = 0;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int idx) {
	if(tt[idx].cnt) {
		tt[idx].sum = pos[tt[idx].right+1] - pos[tt[idx].left];
	} else if(tt[idx].left == tt[idx].right) {
		tt[idx].sum = 0;
	} else {
		tt[idx].sum = tt[LL(idx)].sum + tt[RR(idx)].sum;
	}
}
 
void update(int l,int r,int st,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		tt[idx].cnt += st;
		update(idx);
		return ;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,st,LL(idx));
	if(mid < r)	update(l,r,st,RR(idx));
	update(idx);
}
 
int Bin(double x,int hi) {
	int lo = 0;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(pos[mid] == x)	return mid;
		if(pos[mid] < x) {
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return -1;
}
 
int main() {
	int n;
	int cas = 1;
	while(scanf("%d",&n) == 1) {
		if(n == 0)	break;
		int m = 0;
		FF(i,n) {
			double a,b,c,d;
			scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
			pos[m] = ss[m].left = ss[m+1].left = a;
			ss[m].high = b;
			pos[m+1] = ss[m].right = ss[m+1].right = c;
			ss[m+1].high = d;
			ss[m].side = 1;
			ss[m+1].side = -1;
			m += 2;
		}
		sort(ss,ss+m,cmp);
		sort(pos,pos+m);
		int k = 0;
		FF(i,m) {
			if(i == 0 || pos[i] != pos[i-1]) {
				pos[k++] = pos[i];
			}
		}
		build(0,k-1,1);
		double ret = 0;
		FF(i,m-1) {
			int l = Bin(ss[i].left,k-1);
			int r = Bin(ss[i].right,k-1) - 1;
			if(l > r) {
				ret += tt[1].sum * (ss[i+1].high - ss[i].high);
				continue;
			}
			update(l,r,ss[i].side,1);
			ret += tt[1].sum * (ss[i+1].high - ss[i].high);
		}
		printf("Test case #%d\n",cas++);
		printf("Total explored area: %.2lf\n\n",ret);
	}
	return 0;	
}

.
15.hdu1255 覆盖的面积
同上,扫描线法,我多加了一个系数csum,来统计覆盖两次的长度(156MS,第一次做线段树排到第一,纪念下)

^?View Code CPP

struct Seg_Tree{
	int left,right;
	double sum;
	double csum;
	int cnt;
	int mid() {
		return (left + right) >> 1;
	}
}tt[6000];
struct Seg{
	double left,right,high;
	int side;
}ss[2001];
int k;
double pos[2001];
bool cmp(Seg &a,Seg &b) {
	return a.high < b.high;
}
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].sum = 0;
	tt[idx].csum = 0;
	tt[idx].cnt = 0;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int idx) {
	if(tt[idx].cnt > 0) {
		tt[idx].sum = pos[tt[idx].right + 1] - pos[tt[idx].left];
	} else if(tt[idx].left == tt[idx].right) {
		tt[idx].sum = 0;
	} else {
		tt[idx].sum = tt[LL(idx)].sum + tt[RR(idx)].sum;
	}
 
	if(tt[idx].cnt > 1) {
		tt[idx].csum = pos[tt[idx].right + 1] - pos[tt[idx].left];
	} else if(tt[idx].left == tt[idx].right) {
		tt[idx].csum = 0;
	} else if(tt[idx].cnt > 0) {
		tt[idx].csum = tt[LL(idx)].sum + tt[RR(idx)].sum;
	} else {
		tt[idx].csum = tt[LL(idx)].csum + tt[RR(idx)].csum;
	}
}
 
void update(int l,int r,int st,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		tt[idx].cnt += st;
		update(idx);
		return ;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,st,LL(idx));
	if(mid < r)	update(l,r,st,RR(idx));
	update(idx);
}
 
int Bin(double x) {
	int hi = k - 1;
	int lo = 0;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(pos[mid] == x) {
			return mid;
		}
		if(pos[mid] < x) {
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return -1;
}
int main() {
	int T;
	scanf("%d",&T);
	while(T --) {
		int n;
		scanf("%d",&n);
		int m = 0;
		FF(i,n) {
			double a,b,c,d;
			scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
			pos[m] = ss[m].left = ss[m+1].left = a;
			ss[m].high = b;
			pos[m+1] = ss[m].right = ss[m+1].right = c;
			ss[m+1].high = d;
			ss[m].side = 1;
			ss[m+1].side = -1;
			m += 2;
		}
		sort(ss,ss+m,cmp);
		sort(pos,pos+m);
		k = 0;
		FF(i,m) {
			if(i == 0 || pos[i] != pos[i-1]) {
				pos[k++] = pos[i];
			}
		}
		build(0,k-1,1);
		double ans = 0;
		FF(i,m-1) {
			if(ss[i].left == ss[i].right) {
				ans += tt[1].sum * (ss[i+1].high - ss[i].high);
				continue;
			}
			int l = Bin(ss[i].left);
			int r = Bin(ss[i].right) - 1;
			update(l,r,ss[i].side,1);
			ans += tt[1].csum * (ss[i+1].high - ss[i].high);
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}

.
16.hdu1828 Picture
扫描线,同面积统计,加了一个num_Seg统计一个扫描区域里的边

^?View Code CPP

struct Seg_Tree{
	int left,right;
	int lbd,rbd;
	int cnt;
	int Len;
	int num_Seg;
	int mid() {
		return (left + right) >> 1;
	}
}tt[66666];
struct Seg{
	int left;
	int right;
	int high;
	int side;
}ss[10001];
 
bool cmp(Seg &a,Seg &b) {
	return a.high < b.high;
}
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].cnt = tt[idx].Len = tt[idx].num_Seg = 0;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int idx) {
	if(tt[idx].cnt) {
		tt[idx].lbd = tt[idx].rbd = 1;
		tt[idx].Len = tt[idx].right - tt[idx].left + 1;
		tt[idx].num_Seg = 2;
	} else if(tt[idx].left == tt[idx].right) {
		tt[idx].lbd = tt[idx].rbd = 0;
		tt[idx].Len = 0;
		tt[idx].num_Seg = 0;
	} else {
		int l = LL(idx);
		int r = RR(idx);
		tt[idx].lbd = tt[l].lbd;
		tt[idx].rbd = tt[r].rbd;
		tt[idx].Len = tt[l].Len + tt[r].Len;
		tt[idx].num_Seg = tt[l].num_Seg + tt[r].num_Seg - 2 * (tt[l].rbd & tt[r].lbd);
	}
}
 
void update(int l,int r,int st,int idx) {
	if(tt[idx].left >= l && tt[idx].right <= r) {
		tt[idx].cnt += st;
		update(idx);
		return ;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,st,LL(idx));
	if(mid < r)	update(l,r,st,RR(idx));
	update(idx);
}
 
int main() {
	int n;
	while(scanf("%d",&n) == 1) {
		if(n == 0) {
			puts("0");
			continue;
		}
		int lup = 10000;
		int rup = -10000;
		int m = 0;
		FF(i,n) {
			scanf("%d%d%d%d",&ss[m].left,&ss[m].high,&ss[m].right,&ss[m+1].high);
			ss[m+1].left = ss[m].left;
			ss[m+1].right = ss[m].right;;
			ss[m].side = 1;
			ss[m+1].side = -1;
			lup = min(lup,ss[m].left);
			rup = max(rup,ss[m].right);
			m += 2;
		}
		sort(ss,ss+m,cmp);
		build(lup,rup-1,1);
		int ans = 0;
		int buf = 0;
		ss[m] = ss[m-1];
		FF(i,m) {
			if(ss[i].left != ss[i].right) {
				update(ss[i].left,ss[i].right-1,ss[i].side,1);
			}
			ans += tt[1].num_Seg * (ss[i+1].high - ss[i].high);
			ans += abs(tt[1].Len - buf);
			buf = tt[1].Len;
		}
		printf("%d\n",ans);
	}
	return 0;
}

.
17.pku1436 Horizontally Visible Segments
成段更新,成段询问(染色问题,坐标*2后很简单,最后统计用暴力- -)

^?View Code CPP

struct Seg_Tree{
	int left,right;
	int col;
	int mid() {
		return (left + right) >> 1;
	}
}tt[80000];
#define mix -1
struct Seg{
	int pos,left,right;
}hh[8888];
vector <int> edge[8888];
int hash[8888];
int cnt[8888];
bool cmp(Seg &a,Seg &b) {
	return a.pos < b.pos;
}
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].col = mix;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int l,int r,int id,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		tt[idx].col = id;
		return ;
	}
	if(tt[idx].col != mix) {
		tt[LL(idx)].col = tt[RR(idx)].col = tt[idx].col;
		tt[idx].col = mix;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,id,LL(idx));
	if(mid < r)	update(l,r,id,RR(idx));
}
 
void query(int l,int r,int id,int idx) {
	if(tt[idx].col != mix) {
		if(hash[tt[idx].col] != id) {
			edge[tt[idx].col].push_back(id);
			hash[tt[idx].col] = id;
		}
		return ;
	}
	if(tt[idx].left == tt[idx].right)	return ;
	if(tt[idx].col != mix) {
		tt[LL(idx)].col = tt[RR(idx)].col = tt[idx].col;
		tt[idx].col = mix;
	}
	int mid = tt[idx].mid();
	if(r <= mid) {
		query(l,r,id,LL(idx));
	} else if(mid < l) {
		query(l,r,id,RR(idx));
	} else {
		query(l,mid,id,LL(idx));
		query(mid+1,r,id,RR(idx));
	}
}
 
int main() {
	int T;
	scanf("%d",&T);
	while(T --) {
		int n;
		build(0,16000,1);
		scanf("%d",&n);
		FF(i,n) {
			scanf("%d%d%d",&hh[i].left,&hh[i].right,&hh[i].pos);
			hh[i].left *= 2;
			hh[i].right *= 2;
			edge[i].clear();
		}
		sort(hh,hh+n,cmp);
		CC(hash,-1);
		FF(i,n) {
			query(hh[i].left,hh[i].right,i,1);
			update(hh[i].left,hh[i].right,i,1);
		}
		int ans = 0;
		FF(i,n) {
			int m = sz(edge[i]);
			FF(j,m) {
				int idx = edge[i][j];
				int mm = sz(edge[idx]);
				FF(k,m) {
					FF(l,mm) {
						if(edge[i][k] == edge[idx][l]) {
							ans ++;
						}
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

.
18.pku3225 Help with Intervals
成段更新,总询问区间(有个异或操作比较新颖)

^?View Code CPP

#define mix -1
struct Seg_Tree{
	int left;
	int right;
	int cover;
	int change;
	int mid() {
		return (left + right) >> 1;
	}
	void Change() {
		if(change) {
			change = 0;
		} else if(cover != mix) {
			cover ^= 1;
		} else {
			change = 1;
		}
	}
}tt[800000];
bool hash[131072];
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].cover = 0;
	tt[idx].change = 0;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void Scanf(int &a,int &b,char str[]) {
	int pos = 1;
	while(isdigit(str[pos])) {
		a = a * 10 + str[pos] - '0';
		pos ++;
	}
	pos ++;
	while(isdigit(str[pos])) {
		b = b * 10 + str[pos] - '0';
		pos ++;
	}
	if(str[0] == '(') {
		a = a * 2 + 1;
	} else {
		a = a * 2;
	}
	if(str[pos] == ')') {
		b = b * 2 - 1;
	} else {
		b = b * 2;
	}
}
 
void Printf(int a,int b) {
	if(a%2 == 0) {
		printf("[%d,",a/2);
	} else {
		printf("(%d,",a/2);
	}
	if(b%2 == 0) {
		printf("%d]",b/2);
	} else {
		printf("%d)",b/2+1);
	}
}
 
void update(int l,int r,char op,int idx) {
 
	int mid;
	switch(op) {
		case 'U':
			if(l == tt[idx].left && r == tt[idx].right) {
				tt[idx].cover = 1;
				tt[idx].change = false;
				return ;
			}
			if(tt[idx].cover != mix) {
				tt[LL(idx)].cover = tt[RR(idx)].cover = tt[idx].cover;
				tt[LL(idx)].change = tt[RR(idx)].change = 0;
				tt[idx].cover = mix;
			}
			break;
		case 'I':
			if(l == tt[idx].left && r == tt[idx].right) {
				return ;
			}
			if(tt[idx].cover != mix) {
				tt[LL(idx)].cover = tt[RR(idx)].cover = tt[idx].cover;
				tt[LL(idx)].change = tt[RR(idx)].change = 0;
				tt[idx].cover = mix;
			}
			mid = tt[idx].mid();
			if(r <= mid)	tt[RR(idx)].cover = tt[idx].change;
			if(mid < l)		tt[LL(idx)].cover = tt[idx].change;
			break;
		case 'D':
			if(l == tt[idx].left && r == tt[idx].right) {
				tt[idx].cover = 0;
				tt[idx].change = false;
				return ;
			}
			if(tt[idx].cover != mix) {
				tt[LL(idx)].cover = tt[RR(idx)].cover = tt[idx].cover;
				tt[LL(idx)].change = tt[RR(idx)].change = 0;
				tt[idx].cover = mix;
			}
			break;
		case 'C':
			if(l == tt[idx].left && r == tt[idx].right) {
				tt[idx].Change();
				return ;
			}
			if(tt[idx].cover != mix) {
				tt[LL(idx)].cover = tt[RR(idx)].cover = tt[idx].cover;
				tt[LL(idx)].change = tt[RR(idx)].change = 0;
				tt[idx].cover = mix;
			}
			mid = tt[idx].mid();
			if(r <= mid)	tt[RR(idx)].cover = tt[idx].change;
			if(mid < l)		tt[LL(idx)].cover = tt[idx].change;
			break;
		case 'S':
			if(l == tt[idx].left && r == tt[idx].right) {
				tt[idx].Change();
				return ;
			}
			if(tt[idx].cover != mix) {
				tt[LL(idx)].cover = tt[RR(idx)].cover = tt[idx].cover;
				tt[LL(idx)].change = tt[RR(idx)].change = 0;
				tt[idx].cover = mix;
			}
			break;
	}
	if(tt[idx].change) {
		tt[LL(idx)].Change();
		tt[RR(idx)].Change();
		tt[idx].change = 0;
	}
	mid = tt[idx].mid();
	if(r <= mid) {
		update(l,r,op,LL(idx));
	} else if(mid < l) {
		update(l,r,op,RR(idx));
	} else {
		update(l,mid,op,LL(idx));
		update(mid+1,r,op,RR(idx));
	}
	if(tt[LL(idx)].cover == tt[RR(idx)].cover) {
		tt[idx].cover = tt[LL(idx)].cover;
	}
}
 
void query(int l,int r,int idx) {
	if(l == r) {
		if(tt[idx].cover) {
			hash[l] = true;
		}
		return ;
	}
	if(tt[idx].cover != mix) {
		tt[LL(idx)].cover = tt[RR(idx)].cover = tt[idx].cover;
		tt[LL(idx)].change = tt[RR(idx)].change = 0;
		tt[idx].cover = mix;
	}
	if(tt[idx].change) {
		tt[LL(idx)].Change();
		tt[RR(idx)].Change();
		tt[idx].change = 0;
	}
	int mid = tt[idx].mid();
	query(l,mid,LL(idx));
	query(mid+1,r,RR(idx));
}
 
int M = 131072;
int main() {
	build(0,M,1);
	char op[2];
	char str[99];
	while(scanf("%s%s",op,str) == 2) {
		int a(0),b(0);
		Scanf(a,b,str);
		if(a > b) {
			if(op[0] == 'C' || op[0] == 'I') {
				tt[1].cover = 0;
				tt[1].change = 0;
			}
			continue;
		}
		update(a,b,op[0],1);
	}
	CC(hash,false);
	query(0,M,1);
	bool flag = false;
	int start = -1,end;
	FF(i,M) {
		if(hash[i]) {
			if(start == -1) {
				start = i;
			}
			end = i;
		} else {
			if(start != -1) {
				if(flag)	printf(" ");
				flag = true;
				Printf(start,end);
				start = -1;
			}
		}
	}
	if(!flag) {
		printf("empty set");
	}
	puts("");
	return 0;
}

.
19.pku2482 Stars in Your Window
成段更新,区间最值 + 扫描线(转化成区间最值有点巧妙,数据太TMD的恶心了,中间二分的地方会int溢出,检查了半个小时)

^?View Code CPP

struct Seg_Tree{
	int left,right;
	int val;
	int add;
	int mid() {
		return (left + right)>>1;
	}
}tt[40000];
struct star{
	int x,y,val;
}hh[10001];
int pos[10001];
int n , m , H, W;
bool cmp(star &a,star &b) {
	return a.y < b.y;
}
 
int Bin(LL x) {
	int lo = 0;
	int hi = m - 1;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(pos[mid] < x) {
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return lo;
}
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].add = 0;
	tt[idx].val = 0;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int l,int r,int add,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		tt[idx].add += add;
		tt[idx].val += add;
		return ;
	}
	if(tt[idx].add) {
		tt[LL(idx)].add += tt[idx].add;
		tt[RR(idx)].add += tt[idx].add;
		tt[LL(idx)].val += tt[idx].add;
		tt[RR(idx)].val += tt[idx].add;
		tt[idx].add = 0;
	}
	int mid = tt[idx].mid();
	if(l <= mid) update(l,r,add,LL(idx));
	if(mid < r) update(l,r,add,RR(idx));
	tt[idx].val = max(tt[LL(idx)].val , tt[RR(idx)].val);
}
 
int main() {
	while(scanf("%d%d%d",&n,&W,&H) == 3) {
		FF(i,n) {
			scanf("%d%d%d",&hh[i].x,&hh[i].y,&hh[i].val);
			pos[i] = hh[i].x;
		}
		sort(hh,hh+n,cmp);
		sort(pos,pos+n);
		m = 0;
		FF(i,n) {
			if(i == 0 || pos[i] != pos[i-1]) {
				pos[m++] = pos[i];
			}
		}
		build(0,m-1,1);
		int start = 0,end = 0;
		int ans = 0;
		FF(i,n) {
			if(i && hh[i].y == hh[i-1].y)	continue;
			FOR(j,start,i) {
				update(Bin(hh[j].x) , Bin(hh[j].x + W) - 1, -hh[j].val , 1);
			}
			start = i;
			int lo = i;
			int hi = n-1;
			LL buf = (LL)hh[i].y + H;
			while(lo <= hi) {
				int mid = (lo + hi) >> 1;
				if(hh[mid].y < buf) {
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			}
			FOR(j,end,lo) {
				update(Bin(hh[j].x) , Bin((LL)hh[j].x + W) - 1, hh[j].val , 1);
			}
			end = lo;
			checkmax(ans,tt[1].val);
			if(end == n)	break;
		}
		printf("%d\n",ans);
	}
	return 0;
}

.
20.pku2828 Buy Tickets
思维很巧妙,倒过来做的话就能确定此人所在的位置

^?View Code CPP

struct Seg_Tree{
	int left,right;
	int remain;
	int mid() {
		return (left + right) >> 1;
	}
}tt[600000];
 
int pos[200001];
int newpos[200001];
int val[200001];
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].remain = r - l + 1;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
int query(int id,int idx) {
	tt[idx].remain --;
	if(tt[idx].left == tt[idx].right) {
		return tt[idx].left;
	}
	if(tt[LL(idx)].remain >= id) {
		return query(id,LL(idx));
	} else {
		return query(id-tt[LL(idx)].remain,RR(idx));
	}
}
 
int main() {
	int n;
	while(scanf("%d",&n) == 1) {
		build(0,n-1,1);
		FF(i,n) {
			scanf("%d%d",&pos[i],&val[i]);
		}
		FFD(i,n) {
			newpos[query(pos[i]+1,1)] = i;
		}
		FF(i,n-1) {
			printf("%d ",val[newpos[i]]);
		}
		printf("%d\n",val[newpos[n-1]]);
	}
	return 0;
}

.
21.pku2464 Brownie Points II
更新节点,区间求和 + 扫描线(很好玩的一道题目,用两个线段树沿着扫描线更新,然后按”自己最多,对方最少”的方案一路统计)
(因为两棵树,我就直接写成类了)

^?View Code CPP

class Key {
private:
	struct Seg_Tree{
		int left;
		int right;
		int sum;
		int mid() {
			return (left + right) >> 1;
		}
	}tt[600000];
public:
	void build(int l,int r,int idx) {
		tt[idx].left = l;
		tt[idx].right = r;
		tt[idx].sum = 0;
		if(l == r)	return ;
		int mid = tt[idx].mid();
		build(l,mid,LL(idx));
		build(mid+1,r,RR(idx));
	}
	void update(int pos,int st,int idx) {
		if(tt[idx].left == tt[idx].right) {
			tt[idx].sum += st;
			return ;
		}
		int mid = tt[idx].mid();
		if(pos <= mid) {
			update(pos,st,LL(idx));
		} else {
			update(pos,st,RR(idx));
		}
		tt[idx].sum = tt[LL(idx)].sum + tt[RR(idx)].sum;
	}
	int query(int l,int r,int idx) {
		if(l == tt[idx].left && r == tt[idx].right) {
			return tt[idx].sum;
		}
		int mid = tt[idx].mid();
		if(r <= mid) {
			return query(l,r,LL(idx));
		} else if(mid < l) {
			return query(l,r,RR(idx));
		} else {
			return query(l,mid,LL(idx)) + query(mid+1,r,RR(idx));
		}
	}
}Left,Right;
 
struct Point {
	int x,y;
}p[200001];
int pos[200010];
bool cmp(Point &a,Point &b) {
	return a.x < b.x;
}
int m;
int Bin(int x) {
	int lo = 1;
	int hi = m - 1;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(pos[mid] == x) {
			return mid;
		}
		if(pos[mid] < x) {
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return -1;
}
 
vector <int> ans;
 
int main() {
	int n;
	while(scanf("%d",&n) == 1) {
		if(n == 0)	break;
		FF(i,n) {
			scanf("%d%d",&p[i].x,&p[i].y);
			pos[i+1] = p[i].y;
		}
		sort(pos+1,pos+n+1);
		sort(p,p+n,cmp);
		m = 1;
		FOR(i,1,n+1) {
			if(i == 1 || pos[i] != pos[i-1]) {
				pos[m++] = pos[i];
			}
		}
		Left.build(0,m,1);
		Right.build(0,m,1);
		FF(i,n) {
			Right.update(Bin(p[i].y),1,1);
		}
		int start = 0;
		int best = 0;
		ans.clear();
		FOR(i,1,n+1) {
			if(i == n || p[i].x != p[i-1].x) {
				FOR(j,start,i) {
					Right.update(Bin(p[j].y),-1,1);
				}
				int Ollie = -1;
				int Stan = -1;
				FOR(j,start,i) {
					int idx = Bin(p[j].y);
					int A = Left.query(0,idx-1,1) + Right.query(idx+1,m,1);
					int B = Left.query(idx+1,m,1) + Right.query(0,idx-1,1);
					if(Ollie == B) {
						Stan = min(Stan , A);
					} else if(Ollie < B) {
						Ollie = B;
						Stan = A;
					}
				}
				if(Stan > best) {
					best = Stan;
					ans.clear();
				}
				if(Stan == best) {
					ans.push_back(Ollie);
				}
				FOR(j,start,i) {
					Left.update(Bin(p[j].y),1,1);
				}
				start = i;
			}
		}
		printf("Stan: %d; Ollie:",best);
		sort(ans.begin(),ans.end());
		FF(i,sz(ans)) {
			if(i == 0 || ans[i] != ans[i-1]) {
				printf(" %d",ans[i]);
			}
		}
		puts(";");
	}
	return 0;
}

.
22.pku3145 Harmony Forever
查找一个区间内最左边的数,询问的val大的话用线段树,小的话线性扫描,很囧的题目

^?View Code CPP

struct Seg_Tree{
	int left,right;
	bool exist;
	bool unexist;
	int mid() {
		return (left + right) >> 1;
	}
}tt[2000000];
int num[40010];
int rank[5000001];
#define M 50000
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].exist = false;
	tt[idx].unexist = false;
	if(l == r) return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int id,int idx) {
	tt[idx].exist = true;
	if(tt[idx].left == tt[idx].right) {
		return ;
	}
	if(tt[idx].unexist) {
		tt[LL(idx)].unexist = tt[RR(idx)].unexist = true;
		tt[LL(idx)].exist = tt[RR(idx)].exist = false;
		tt[idx].unexist = false;
	}
	int mid = tt[idx].mid();
	if(id <= mid) {
		update(id,LL(idx));
	} else {
		update(id,RR(idx));
	}
}
 
int query(int l,int r,int idx) {
	if(tt[idx].left == tt[idx].right) {
		return tt[idx].left;
	}
	if(tt[idx].unexist) {
		tt[LL(idx)].unexist = tt[RR(idx)].unexist = true;
		tt[LL(idx)].exist = tt[RR(idx)].exist = false;
		tt[idx].unexist = false;
	}
	int mid = tt[idx].mid();
	int buf = -1;
	if(l <= mid) {
		if(tt[LL(idx)].exist) {
			buf = query(l,r,LL(idx));
		}
	}
	if(buf != -1)	return buf;
	if(mid < r) {
		if(tt[RR(idx)].exist) {
			buf = query(l,r,RR(idx));
		}
	}
	return buf;
}
 
int main() {
	build(0,500000,1);
	int T, cas = 1;
	while(scanf("%d",&T) == 1) {
		if(T == 0)	break;
		if(cas != 1) {
			puts("");
		}
		printf("Case %d:\n",cas++);
		tt[1].unexist = true;
		int n = 0;
		while(T --) {
			char op[2];
			int val;
			scanf("%s%d",op,&val);
			if(op[0] == 'B') {
				update(val,1);
				num[n++] = val;
				rank[val] = n;
			} else {
				if(n == 0) {
					puts("-1");
					continue;
				}
				if(val <= 1000) {
					int remain = val;
					int last = -1;
					FFD(i,n) {
						int buf = num[i] % val;
						if(buf < remain) {
							remain = buf;
							last = i+1;
						}
						if(remain == 0) {
							break;
						}
					}
					printf("%d\n",last);
				} else {
					int remain = val;
					int last = -1;
					int start = 0;
					int end = val - 1;
					while(start <= 500000) {
						checkmin(end,500000);
						int key = query(start,end,1);
						if(key != -1) {
							int buf = key % val;
							if(buf < remain) {
								remain = buf;
								last = rank[key];
							} else if(buf == remain) {
								checkmax(last,rank[key]);
							}
						}
						start += val;
						end += val;
					}
					printf("%d\n",last);
				}
			}
		}
	}
	return 0;
}

.
23.pku2886 Who Gets the Most Candies?
寻找区间中的左数第N个数,约瑟夫环(学到了反素数表,可以不用把所有数字预处理出来了)

^?View Code CPP

struct Seg_Tree{
	int left,right;
	int sum;
	int mid() {
		return (left + right) >> 1;
	}
}tt[1100000];
struct H{
	char name[12];
	int val;
}hh[500001];
 
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].sum = (r - l + 1);
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
int update(int k,int idx) {
	tt[idx].sum --;
	if(tt[idx].left == tt[idx].right) {
		return tt[idx].left;
	}
	int mid = tt[idx].mid();
	if(k <= tt[LL(idx)].sum) return update(k,LL(idx));
	return update(k-tt[LL(idx)].sum,RR(idx));
}
 
const int antiprime[] = {1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320, 221760, 277200, 332640, 498960, 554400, 665280};
const int factorNum[] = {1, 2, 3, 4, 6, 8, 9, 10, 12, 16, 18, 20, 24, 30, 32, 36, 40, 48, 60, 64, 72, 80, 84, 90, 96, 100, 108, 120, 128, 144, 160, 168, 180, 192, 200, 216, 224};
 
int main() {
	int n , k, &mod = tt[1].sum;
	while(scanf("%d%d",&n,&k) == 2) {
		FOR(i,1,n+1) {
			scanf("%s%d",hh[i].name,&hh[i].val);
		}
		build(1,n,1);
 
        int tag=0;
		while(antiprime[tag] <= n) {
            tag++;
		}
        int need = antiprime[--tag];
 
		int pos = 0;
		hh[pos].val = 0;
		while(need --) {
			if(hh[pos].val > 0) {
				k = ((k + hh[pos].val - 2)%mod + mod)%mod + 1;
			} else {
				k = ((k + hh[pos].val - 1)%mod + mod)%mod + 1;
			}
			pos = update(k,1);
		}
		printf("%s %d\n",hh[pos].name,factorNum[tag]);
	}
	return 0;
}

.
24.pku2991 Crane
记录了线段的两端点以及转过的角度,成段的转,超有意思的题目,做了之后会对线段树理解更深刻
(wy教主推荐的,不过我的代码写的太搓了..没啥学习的价值)

^?View Code CPP

#define M 10001
struct Point {
	double x,y;
	Point operator + (Point a) {
		Point ret;
		ret.x = x + a.x;
		ret.y = y + a.y;
		return ret;
	}
	Point operator - (Point a) {
		Point ret;
		ret.x = x - a.x;
		ret.y = y - a.y;
		return ret;
	}
};
struct Seg_Tree{
	int left,right;
	int angle;
	Point s,e;
	bool cover;
	int mid() {
		return (left + right) >> 1;
	}
	void turn(int angle) {
		Point ret = s;
		Point buf = s;
		e.x -= s.x;
		e.y -= s.y;
		buf.x = cos(angle*Pi/180);
		buf.y = sin(angle*Pi/180);
		ret.x += e.x*buf.x - e.y*buf.y;
		ret.y += e.x*buf.y + e.y*buf.x;
		e = ret;
	}
}tt[M*4];
int len[M];
int sum[M];
void build(int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].s.x = 0;
	tt[idx].s.y = sum[l]-len[l];
	tt[idx].e.x = 0;
	tt[idx].e.y = sum[r];
	tt[idx].angle = 0;
	tt[idx].cover = false;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update(int idx) {
	int l = LL(idx);
	int r = RR(idx);
	tt[l].angle = (tt[l].angle + tt[idx].angle)%360;
	tt[l].e = tt[l].e + tt[idx].s - tt[l].s;
	tt[l].s = tt[idx].s;
	tt[l].turn(tt[idx].angle);
	tt[l].cover = true;
 
	tt[r].e = tt[r].e + tt[l].e - tt[r].s;
	tt[r].s = tt[l].e;
	tt[r].angle = (tt[r].angle + tt[idx].angle)%360;
	tt[r].turn(tt[idx].angle);
	tt[r].cover = true;
 
	tt[idx].angle = 0;
	tt[idx].cover = false;
}
 
void update(int l,int a,int idx) {
	if(tt[idx].left == l) {
		tt[idx].angle = (tt[idx].angle + a)%360;
		tt[idx].turn(a);
		tt[idx].cover = true;
		return ;
	}
	if(tt[idx].cover) {
		update(idx);
	}
	int mid = tt[idx].mid();
	if(l <= mid) {
		update(l,a,LL(idx));
		tt[RR(idx)].e = tt[RR(idx)].e + tt[LL(idx)].e - tt[RR(idx)].s;
		tt[RR(idx)].s = tt[LL(idx)].e;
		update(mid+1,a,RR(idx));
	} else {
		update(l,a,RR(idx));
	}
	tt[idx].e = tt[RR(idx)].e;
}
 
int query(int id,int idx) {
	if(tt[idx].left == tt[idx].right) {
		return tt[idx].angle;
	}
	if(tt[idx].cover) {
		update(idx);
	}
	int mid = tt[idx].mid();
	if(id <= mid) {
		return query(id,LL(idx));
	} else {
		return query(id,RR(idx));
	}
	tt[idx].e = tt[RR(idx)].e;
}
 
int main() {
	int n , m;
	int cas = 0;
	while(scanf("%d%d",&n,&m) == 2) {
		if(cas) puts("");
		cas ++;
		FOR(i,1,n+1) {
			scanf("%d",&len[i]);
			sum[i] = sum[i-1] + len[i];
		}
		build(1,n,1);
		while(m --) {
			int id,a;
			scanf("%d%d",&id,&a);
			a = ((180 - query(id+1,1) + query(id,1) + a) % 360 + 360)%360;
			update(id+1,a,1);
			printf("%.2lf %.2lf\n",tt[1].e.x+eps,tt[1].e.y+eps);
		}
	}
	return 0;
}

.
25.hdu1823 Luck and Love
二维线段树,没啥意思,代码量大了一倍而已,题目和运用范围都没一维的广,随便找了道题目练习下就好

^?View Code CPP

struct Sub_Seg_Tree {
	int left;
	int right;
	int val;
	int mid() {
		return (left + right) >> 1;
	}
};
struct Seg_Tree{
	int left;
	int right;
	Sub_Seg_Tree tt[1001*4];
	int mid() {
		return (left + right) >> 1;
	}
}tt[101*4];
 
void build2(Sub_Seg_Tree tt[],int l,int r,int idx) {
	tt[idx].left = l;
	tt[idx].right = r;
	tt[idx].val = -1;
	if(l == r)	return ;
	int mid = tt[idx].mid();
	build2(tt,l,mid,LL(idx));
	build2(tt,mid+1,r,RR(idx));
}
 
void build(int l,int r,int idx) {
	build2(tt[idx].tt,0,1000,1);
	tt[idx].left = l;
	tt[idx].right = r;
	if(l == r) return ;
	int mid = tt[idx].mid();
	build(l,mid,LL(idx));
	build(mid+1,r,RR(idx));
}
 
void update2(Sub_Seg_Tree tt[],int b,int val,int idx) {
	if(tt[idx].left == tt[idx].right) {
		checkmax(tt[idx].val,val);
		return ;
	}
	if(b <= tt[idx].mid()) {
		update2(tt,b,val,LL(idx));
	} else {
		update2(tt,b,val,RR(idx));
	}
	tt[idx].val = max(tt[LL(idx)].val,tt[RR(idx)].val);
}
 
void update(int a,int b,int val,int idx) {
	update2(tt[idx].tt,b,val,1);
	if(tt[idx].left == tt[idx].right) return ;
	if(a <= tt[idx].mid()) {
		update(a,b,val,LL(idx));
	} else {
		update(a,b,val,RR(idx));
	}
}
 
int query2(Sub_Seg_Tree tt[],int l,int r,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		return tt[idx].val;
	}
	int mid = tt[idx].mid();
	int ret = -1;
	if(l <= mid) checkmax(ret,query2(tt,l,r,LL(idx)));
	if(mid < r) checkmax(ret,query2(tt,l,r,RR(idx)));
	return ret;
}
 
int query(int l,int r,int l2,int r2,int idx) {
	if(l <= tt[idx].left && r >= tt[idx].right) {
		return query2(tt[idx].tt,l2,r2,1);
	}
	int mid = tt[idx].mid();
	int ret = -1;
	if(l <= mid) checkmax(ret,query(l,r,l2,r2,LL(idx)));
	if(mid < r) checkmax(ret,query(l,r,l2,r2,RR(idx)));
	return ret;
}
 
int main() {
	int T;
	while(scanf("%d",&T) == 1) {
		if(T == 0)	break;
		build(100,200,1);
		while(T --) {
			char op;
			while(!isalpha(op = getchar()));
			if(op == 'I') {
				int a;
				double b,c;
				scanf("%d%lf%lf",&a,&b,&c);
				update(a,int(b*10),int(c*10),1);
			} else {
				int l1,r1;
				double l2,r2;
				scanf("%d%d%lf%lf",&l1,&r1,&l2,&r2);
				if(l1 > r1) swap(l1,r1);
				if(l2 > r2) swap(l2,r2);
				int ret = query(l1,r1,int(l2*10),int(r2*10),1);
				if(ret < 0) {
					puts("-1");
				} else {
					printf("%.1lf\n",ret/10.0);
				}
			}
		}
	}
	return 0;
}

Popularity: 100% [?]

code, Seg_Tree, Template, 专辑, 线段树

这篇文章由shǎ崽于2009/11/23 19:56发表在Special Topic。你可以订阅RSS 2.0 也可以发表评论或引用到你的网站。

相关文章
引用（2）
评论（49）

#1 昵称(必须)
大约1周前

回复引用

我也在郁闷第十道题（poj 3667）！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

[回复]
#2 jj
大约2周前

回复引用

大牛。能做个hash的专辑吗？

[回复]
#3 昵称(必须)
大约1月前

回复引用

楼主第10题代码有误，试试下面的测试数据：
10 6
1 10
2 1 2
2 9 2
1 3
在这里应该输出0，但输出的是1，并且如果一直输入1 3的话，会一直输出1

[回复]
#4 abilitytao
大约1月前

回复引用

不错的总结。。正需要。。。

[回复]
#5 AekdyCoin
大约1月前

回复引用

Orz！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

[回复]
#6 代码疯子
大约1月前

回复引用

如果能给出一个讲解线段树入门的文档，将会更完美

[回复]
#7 xxs2010
大约1月前

回复引用

Orz!!假期训练有得做了！感谢大神的这篇文章！！

[回复]
#8 Euclid
大约1月前

回复引用

谢谢大牛的线段树专辑

[回复]
#9 rommy
大约1月前

回复引用

hotel那题，是怎么求得最左的连续空当？
能不说的详细一点？

[回复]
#10 CrazyAC
大约2月前

回复引用

很好，很强大！！！
这几天刷不完大神的这些题，放假就不回家了，55555

[回复]
shǎ崽回复:
七月 2nd, 2010 at 19:08
呵呵~那要加油啊..

[回复]
CrazyAC 回复:
七月 8th, 2010 at 11:58
哎呀，大牛博客装修了 = =
继续纠结的线段树。。。。。

[回复]
shǎ崽回复:
七月 8th, 2010 at 12:27
之前那个一卡背景就悲剧掉字都看不清,不得已只能装修一下

[回复]
#11 匿名
大约2月前

回复引用

我现在只是学会了区间修改，区间查询这个最基本的用法，看到其他的用法都是灵活变形来的，弱弱的问以下，这些是大牛自己想得还是也都是一些经典的用法？

[回复]
shǎ崽回复:
六月 14th, 2010 at 17:36
关于面积和周长的操作是看经典算法得知的.
其他是自己想的…

[回复]
匿名回复:
六月 15th, 2010 at 10:01
谢谢大牛。这段时间在跟着你的专辑学习线段树。现在看到了pku 3667 hotel了。不会啊不会。我问主要是想知道一下这些题是先放一下，等积累多了再来做呢，还是看你的代码做了。。。

[回复]
#12 Large
大约3月前

回复引用

if(tt[idx].st != -1) {
tt[LL(idx)].st = tt[RR(idx)].st = tt[idx].st;
tt[LL(idx)].doit();
tt[RR(idx)].doit();
tt[idx].st = -1;
}
大牛，能解释下这句吗，为什么如果一个区间不是混杂的，更新它左右子树后要把这个区间的状态赋值-1，也就是混杂？

[回复]
Large 回复:
六月 1st, 2010 at 02:00
恩是POJ3667 忘了说了

[回复]
#13 匿名
大约4月前

回复引用

貌似你的杭电1823的代码是错的。。。。。。。

[回复]
notonlysuccess 回复:
五月 1st, 2010 at 02:20
由于我直接把小数*10然后当成整数来处理
所以用G++和C++提交会有精度上的不同

你用用C++提交就能AC

[回复]
匿名回复:
五月 1st, 2010 at 09:51
呵呵谢谢呀

[回复]
#14 D
大约4月前

回复引用

pku2528 Mayor’s posters
用离散化用的很好，学习了

[回复]
shǎ崽回复:
四月 30th, 2010 at 12:07

[回复]
#15 D
大约4月前

回复引用

two()函数
能考下吗

不明白pku2777 Count Color要是two是变为二进制的话，统计如何做到的

[回复]
D 回复:
四月 29th, 2010 at 16:59
位运算加速

有点看明白了，就是1<<（a-1）

[回复]
shǎ崽回复:
四月 30th, 2010 at 12:08
恩，我写的简略了，这好像是我以前加在预定义里的函数，后来觉得没什么用删掉了，以至于我现在都不知道是什么了。。。

[回复]
chen 回复:
七月 21st, 2010 at 10:10
不明白什么是位运算加速，也不明白
int countbit(int n)
{
int c;
for(c=0;n;n>>=1)
c+=n&1;
return c;
}这段函数的意思
胡同学能否解释一下多谢！

[回复]
#16 匿名
大约4月前

回复引用

我不是很懂你的那个HDOJ1540，能否给我讲讲？

[回复]
shǎ崽回复:
四月 30th, 2010 at 12:12
这题我确实写的太烦了点
我是按照Hotel这题的思路写的
如果懂了Hotel这题就能知道我的思路了
据说有非常简单的方法

[回复]
匿名回复:
五月 1st, 2010 at 02:12
我看懂了我的思路是一样的但是实现的时候总是有点问题。。。。

[回复]
#17 JackDavid127
大约4月前

回复引用

可以把pku 2104 K-th Number加上去吗？
.-= JackDavid127´s last blog ..AHOI 2010 Day -2 =-.

[回复]
shǎ崽回复:
四月 30th, 2010 at 12:10
在我另外一篇文章里，专门介绍K-th Numbe的
http://www.notonlysuccess.com/?p=142

[回复]
#18 小小菜鸟
大约4月前

回复引用

orz…

[回复]
#19 小小菜鸟
大约4月前

回复引用

orz…..
真是好东西啊.

[回复]
#20 BloodElf
大约4月前

回复引用

11.hdu1540 Tunnel Warfare
有多case又不写清楚，一直wa。郁闷。后来看了discuss才知道有多case才过了。

[回复]
BloodElf 回复:
四月 23rd, 2010 at 15:26
(发现我们HDU的队员的矩形面积交模板基本都是在最坏情况下更新到底,宁波惨痛的教训啊..)
什么叫做更新到底？

[回复]
shǎ崽回复:
四月 30th, 2010 at 12:13
这句话可以忽视，当时我在发牢骚而已

[回复]
shǎ崽回复:
四月 30th, 2010 at 12:13
额，hdu都是多case的，暂时还不支持多文件

[回复]
#21 Adonis
大约4月前

回复引用

这网页的内容太NB了！！！
膜拜下大牛！！！^_^

[回复]
#22 匿名
大约4月前

回复引用

额明白了是左子树和右子树

[回复]
#23 匿名
大约4月前

回复引用

请问教主 PKU2777 里的 RR（）和 LL（）函数具体是什么作用呢？
two() 我认为是转换为2进制可这两个实在想不明白能解释下否？

[回复]
shǎ崽回复:
四月 19th, 2010 at 20:31
我的代码可读性太差了。以后一定改正。。。

[回复]
#24 小小菜鸟
大约4月前

回复引用

好东西.要了….

[回复]
#25 chjing
大约4月前

回复引用

很好，很强大

[回复]
#26 zhengfy1
大约4月前

回复引用

额。。。PKU3225看不懂啊，大牛要不要解释下？

[回复]
NotOnlySuccess 回复:
四月 12th, 2010 at 15:43
你先把每个操作独立出来，看看应该对应怎么样的变化

[回复]
zhengfy1 回复:
四月 12th, 2010 at 16:33
我实在是半秃啊。。怎么看都看不懂。。我只知道那个AUB和A-B怎么算，其他的实在想不出也看不懂。

[回复]
NotOnlySuccess 回复:
四月 13th, 2010 at 16:32
我们把当前线段树的状态当成S,要操作的区间当成T，那么
U T 将T区间全部变成1
I T 将T区间不变，将[0,a}和{b,65535]变成0
D T 将T区间全部变成0
C T 将T区间中的1变成0，0变成1，将[0,a}和{b,65535]变成0
S T 将T区间中的1变成0，0变成1

其实就是3个操作的组合：
区间全变1
区间全变0
区间1变0，0变1(也就是上文我提到的异或操作)

[回复]
Ascorpior 回复:
七月 14th, 2010 at 21:15
ms你的那个交集的地方，并不是把[0,a}和{b,65535]变为0，可能S并没有覆盖完

[回复]
#27 匿名
大约5月前

回复引用

顶下~
线段树还不熟练，这几天刷刷看。
ps：网站做的不错哦~

[回复]
匿名回复:
四月 10th, 2010 at 00:49
真强，我输入的是: – D 就变成了图片了。。

[回复]
shǎ崽回复:
四月 11th, 2010 at 18:43

[回复]
#28 bloodelf
大约5月前

回复引用

路过求SailorMoon的mm们资料~拜谢

[回复]
NotOnlySuccess 回复:
四月 8th, 2010 at 19:59
她们有什么资料？你如果得到了也发我一份

[回复]
bloodelf 回复:
四月 8th, 2010 at 20:58
大牛你不是hdu的么？我是想认识她们啊~~去年在合肥有一面之缘~ 呵呵

[回复]
bloodelf 回复:
四月 9th, 2010 at 21:35
HOHO~大牛鄙视我了。。。

[回复]
shǎ崽回复:
四月 11th, 2010 at 18:44
这个…贸然公开MM的资料会被MM们pai飞的

[回复]
bloodelf 回复:
四月 12th, 2010 at 20:56
ToT 能否私下告诉我。。。。。。。。。。。呃。。。。QQ284858949

[回复]
#29 shuitu
大约5月前

回复引用

能详细解释下hdu 1828吗

[回复]
shǎ崽回复:
四月 1st, 2010 at 10:15
lbd,rbd表示左边界和右边界
因为算周长的时候两边的边界要额外的计算
并且有时候要合并
所以要用到上边这两个变量来保存
num_Seg表示扫描线区间[i,i+1]内有多少条和y轴平行的边
也要根据lbd和rbd来计算

[回复]
#30 shuitu
大约5月前

回复引用

hdu 1255 1422 不用判断s[i].left==s[i].right 吧，矩形的左右怎么会相等的呢？

[回复]
shǎ崽回复:
四月 1st, 2010 at 10:11
我一般都喜欢建树一直建到点的~这样可以处理任何情况
各有各的习惯，有人喜欢建到最优一段线段

[回复]
#31 intheway
大约5月前

回复引用

请问神牛,POJ2892 Tunnel Warfare 我过了的代码交到HDU1540为什么就TLE? 莫非有什么细节? 谢谢

[回复]
shǎ崽回复:
三月 16th, 2010 at 08:08
可能是HDU的数据比较邪恶吧~~在HDU做题数据要尽量往邪恶的地方想。。具体我也不清除诶

[回复]
#32 intheway
大约5月前

回复引用

好东东,赞博主~

[回复]
#33 FHNstephen
大约6月前

回复引用

终于做完一半了…

[回复]
#34 daizhenyang
大约6月前

回复引用

终于做完前8道了。。泪奔

[回复]
shǎ崽回复:
三月 16th, 2010 at 08:08
D牛太假了

[回复]
#35 vebird
大约6月前

回复引用

大牛~你的HDU 1754还有bug吧~
例如
5 6
1 2 3 4 5
U 5 1
Q 1 5
最大值变小了，没有更新到。。。

[回复]
shǎ崽回复:
三月 3rd, 2010 at 16:11
哦，真的，多谢提醒，每次我都是和最大的比较更新一下，确实有BUG~改正~

[回复]
#36 匿名
大约6月前

回复引用

请问pku1436那个hash的用意是什么？

[回复]
匿名回复:
三月 1st, 2010 at 19:11
哦！我看懂了。。。

[回复]
shǎ崽回复:
三月 3rd, 2010 at 16:18
呵呵~没来得及回复~

[回复]
#37 匿名
大约6月前

回复引用

那个pku3225里的那个change=1，0分别表示的是什么意思啊？
谢谢！

[回复]
NotOnlySuccess 回复:
二月 28th, 2010 at 21:47
就是将这线段上的值全部反一反。。0变成1，1变成0

[回复]
#38 Prowindy
大约7月前

回复引用

poj 3667那题query有个地方有问题，用你的程序试试
1 5
1 1
1 1
1 1
1 1
1 1
会发现每次都可以分配…

[回复]
#39 路人A
大约7月前

回复引用

膜拜牛牛~~~~

[回复]
#40 匿名
大约7月前

回复引用

你的代码说明部分好像没有SS()，这个函数什么意思

[回复]
shǎ崽回复:
一月 31st, 2010 at 16:30
就是一个读入变量的函数，后来我觉得没有必要预定于，就去掉了。
预定义较以前减去了很多不必要的东西。但是这里的代码没有修改

[回复]
匿名回复:
二月 2nd, 2010 at 14:50
后来看懂了，只怪自己不够细心。pku3277也是不错的题目，才刚开始研究线段树。

[回复]
notonlysuccess 回复:
二月 2nd, 2010 at 19:38
呵呵~~

[回复]
#41 匿名
大约7月前

回复引用

膜拜玉树临风，一枝梨花压海棠的shǎ崽教主，教主千秋万代，一统江湖！

[回复]
shǎ崽回复:
一月 31st, 2010 at 16:31
~~~~~~““

[回复]
#42 匿名
大约7月前

回复引用

大牛啊，pku1436为什么要坐标要*2啊？

[回复]
shǎ崽回复:
一月 25th, 2010 at 23:58
不如说
1 4 1
1 2 2
3 4 2
1 4 3
这个例子吧
其实第一条是可以看到第四条线段的，但是不乘以2的话我的方法就判断不出来了~

[回复]
#43 sunhaowen
大约7月前

回复引用

这两天都在刷你这套题。
有个地方写错了，hdu2871你写成2781了，不过幸好你加了题目和链接

[回复]
shǎ崽回复:
一月 24th, 2010 at 11:31
谢谢提醒,常常写错这个,哈哈

[回复]
#44 路人丙
大约7月前

回复引用

跟*2无关，我知道了。。

[回复]
notonlysuccess 回复:
一月 19th, 2010 at 11:19
您的网站真NB~

[回复]
#45 路人丙
大约7月前

回复引用

POJ 1436为什么要用一个hash[]标记？是不是因为坐标*2后可能出现重复？

[回复]
#46 sunhaowen
大约8月前

回复引用

好多题目啊，线段树好久没用了，都有点生疏了，改天去把你这些题做做

[回复]
shǎ崽回复:
一月 9th, 2010 at 11:23
这套题做了基本不怕线段树了

[回复]
#47 dlut_thinkers
大约8月前

回复引用

二维线段树最好还是不要建树，不然复杂度是O(n^2)

[回复]
shǎ崽回复:
十二月 28th, 2009 at 10:47
赞同，有次比赛的时候拍二维的就郁闷到家了

[回复]
#48 Trees poj也不错的
大约8月前

回复引用

大

[回复]
shǎ崽回复:
十二月 12th, 2009 at 11:32
大大~

[回复]
#49 wywcgs
大约9月前

回复引用

建议加一道pku 2991 Crane

[回复]
shǎ崽回复:
十一月 29th, 2009 at 23:33
感谢wy教主推荐,已经加上了

[回复]

网络流专辑

大约9月前 - 9个评论

网络流是ACM里非常重要的一大块,变形非常灵活,这些天仅仅只是做了一点点题目,几个经典模型,冰山一角而已.
图论可不是练两天就能掌握的,所以也就放弃了一口吃成胖子的想法,打一场持...

图论专辑

大约9月前 - 2个评论

图论里包含的东西太多了，我几乎什么都不会
于是我要从最基础的学起- -
这篇文章慢慢更新我学的知识

12.1更新
有向图的强连通
12.3更新
网络流的几个常见算法

第k元素log(n)算法–划分树

大约9月前 - 41个评论

前几天学线段树,这个经典的K-th number一直没有做,关键是听别人说复杂度是log(n)^3,我对这个需要两次二分+一次查找的算法非常的不爽,于是一直拖着没搞
今天正准备着手这题的时候,发现PKU...

test

大约9月前 - 2个评论

测试一下贴代码
顺便把我的模版贴上来,我每段代码基本上都会用到这50行预定义..所以大家看到一道水题我要写几千B的时候不要误会了XD
所以以后我贴出来的代码会少很多头文件很...

一个月时间

大约9月前 - 4个评论

线段树
网络流
AC自动机
模版题:后缀树,最小树形图,最近公共祖先(最后这三个比较水)
大概很多人都不相信上边这些基础应该掌握算法和每个人都有的模板我都不会..但事实...