hdoj1540 Tunnel Warfare

做了一些区间合并,现在已经比较理解了,关键一点是要知道,任何一个连续区,不断向下,一定会被分隔开。
这道题的query,要求包含节点x的1的连续长度。如果m+1-rmax[lson]<=pos && pos<=m+lmax[rson]那么直接返回这一段,否则x所在的连续1区间必定在左子区间或右子区间,继续往下找即可。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=5e4;
int lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
int st[maxn+10],top;
inline int max(int a,int b){return a>b?a:b;}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	mmax[id]=max(mmax[lson],mmax[rson]);
	mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
	if(rmax[rson]==lenr) rmax[id]+=rmax[lson];
	return;
}
void build(int id,int l,int r)
{
	lmax[id]=rmax[id]=mmax[id]=r-l+1;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	return;
}
void update(int id,int l,int r,int pos,int v)
{
	if(l==r)
	{
		lmax[id]=rmax[id]=mmax[id]=v;
		return;
	}
	int m=(l+r)/2;
	if(pos<=m) update(lson,l,m,pos,v);
	else update(rson,m+1,r,pos,v);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int pos)
{
	if(l==r) return mmax[id];
	int m=(l+r)/2;
	if(m+1-rmax[lson]<=pos && pos<=m+lmax[rson]) return rmax[lson]+lmax[rson];
	if(pos<=m) return query(lson,l,m,pos);
	else return query(rson,m+1,r,pos);
}
int main()
{
	int i,j;
	int n,m;
	char com[5];
	int x;
	while(~scanf("%d%d",&n,&m))
	{
		top=0;
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			scanf("%s",com);
			if(com[0]!=’R') scanf("%d",&x);
			else
			{
				if(!top) continue;
				update(1,1,n,st[top--],1);
			}
			if(com[0]==’D') update(1,1,n,x,0),st[++top]=x;
			if(com[0]==’Q') printf("%d\n",query(1,1,n,x));
		}
	}
	return 0;
}

hdoj2871 Memory Control

这题前面部分和hotel那题是差不多的,也是寻找最左边连续的空白,成段更新,但是free时要输出free掉的起始点和结束点,get操作要输出第x个block的起始位置,这就比较烦了。开始用set,发现不行,因为要求kth并删除,我去,,难道要写splay。。这样代码也太长了吧。、果断谷歌之,发现是用vector解决的,vector可以在制定迭代器之前的位置插入元素,但是这样效率是o(n)吧。。。要是有5e4个查询是get x的话,岂不是效率超低?
解决两个问题:
(1)怎样知道unit x是属于哪个block的,可以维护一个域block[],当区间由多个内存块组成时block[id]=-1,block[id]=0表示id区间没有内存块覆盖。
(2)怎样get第x个(block是按起始点排序的)内存块的起始位置,按起始点维护一个vector。如上所述,插入和删除时先二分找到位置。
insert(iter,element);表示在迭代器iter的前面一个位置插入元素element。
这题比较考验耐心。。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=5e4;
int block[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
bool sett[maxn<<2],resett[maxn<<2];
typedef struct Node{
	int begin,len;
	bool operator <(const Node &a) const
	{
		return begin<a.begin;
	}
}Node;
Node mem[maxn+10];
vector<Node> hash;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
void do_sett(int id,int l,int r,int type)
{
	mmax[id]=lmax[id]=rmax[id]=0;
	block[id]=type;
	sett[id]=1;resett[id]=0;
}
void do_resett(int id,int l,int r)
{
	mmax[id]=lmax[id]=rmax[id]=r-l+1;
	block[id]=0;
	resett[id]=1;sett[id]=0;
}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	if(block[lson]!=block[rson]) block[id]=-1;
	else block[id]=block[lson];
	mmax[id]=max(mmax[lson],mmax[rson]);
	mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
	if(rmax[rson]==lenr) rmax[id]+=rmax[lson];
	return;
}
void pushdown(int id,int l,int r)
{
	int m=(l+r)/2;
	if(sett[id]) {do_sett(lson,l,m,block[id]);do_sett(rson,m+1,r,block[id]);sett[id]=0;}
	if(resett[id]) {do_resett(lson,l,m);do_resett(rson,m+1,r);resett[id]=0;}
}
void build(int id,int l,int r)
{
	sett[id]=resett[id]=0;
	lmax[id]=rmax[id]=mmax[id]=r-l+1;
	block[id]=0;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	return;
}
void update_sett(int id,int l,int r,int L,int R,int type)
{
	if(L<=l && r<=R)
	{
		do_sett(id,l,r,type);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update_sett(lson,l,m,L,R,type);
	if(R>m) update_sett(rson,m+1,r,L,R,type);
	pushup(id,l,r);
	return;
}
void update_resett(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
	{
		do_resett(id,l,r);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update_resett(lson,l,m,L,R);
	if(R>m) update_resett(rson,m+1,r,L,R);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int len)
{
	if(mmax[id]<len) return 0;
	if(l==r) return l;
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(mmax[lson]>=len) return query(lson,l,m,len);
	if(rmax[lson]+lmax[rson]>=len) return m+1-rmax[lson];
	return query(rson,m+1,r,len);
}
int query_block(int id,int l,int r,int pos)
{
	if(l==r) return block[id];
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(pos<=m) return query_block(lson,l,m,pos);
	else return query_block(rson,m+1,r,pos);
}
int main()
{
	//freopen("data.in","r",stdin);
	int i,j;
	int n,m;
	char com[10];
	int x;
	vector<Node>::iterator it;
	while(~scanf("%d%d",&n,&m))
	{
		int cc=0;
		if(!hash.empty()) hash.clear();
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			scanf("%s",com);
			if(com[0]!='R') scanf("%d",&x);
			else
			{
				update_resett(1,1,n,1,n);
				printf("Reset Now\n");
				if(!hash.empty()) hash.clear();
			}
			if(com[0]=='N')
			{
				int pos=query(1,1,n,x);
				if(pos)
				{
					cc++;
					mem[cc].begin=pos;mem[cc].len=x;
					it=lower_bound(hash.begin(),hash.end(),mem[cc]);
					hash.insert(it,mem[cc]);
					printf("New at %d\n",pos);
					update_sett(1,1,n,pos,pos+x-1,cc);

				}
				else printf("Reject New\n");
			}
			if(com[0]=='F')
			{
				int ret=query_block(1,1,n,x);
				if(ret==0) printf("Reject Free\n");
				else
				{
					printf("Free from %d to %d\n",mem[ret].begin,mem[ret].begin+mem[ret].len-1);
					update_resett(1,1,n,mem[ret].begin,mem[ret].begin+mem[ret].len-1);
					it=lower_bound(hash.begin(),hash.end(),mem[ret]);
					hash.erase(it);
				}
			}
			if(com[0]=='G')
			{
				if(x>hash.size()) printf("Reject Get\n");
				else printf("Get at %d\n",hash[x-1].begin);
			}
		}
		printf("\n");
	}
	return 0;
}

hdoj3397 Sequence operation

和前面差不多的区间合并,只不多操作多一些,要同时记录1和0的情况

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=5e5;

inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline void swap(int &a,int &b){a^=b;b^=a;a^=b;return;}

int sum[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
int zmmax[maxn<<2],zlmax[maxn<<2],zrmax[maxn<<2];
bool set[maxn<<2],reset[maxn<<2],rev[maxn<<2];

void do_set(int id,int l,int r)
{
	sum[id]=lmax[id]=rmax[id]=mmax[id]=r-l+1;
	zmmax[id]=zlmax[id]=zrmax[id]=0;
	set[id]=1;reset[id]=rev[id]=0;
	return;
}
void do_reset(int id,int l,int r)
{
	sum[id]=lmax[id]=rmax[id]=mmax[id]=0;
	zmmax[id]=zlmax[id]=zrmax[id]=r-l+1;
	reset[id]=1;set[id]=rev[id]=0;
}
void do_rev(int id,int l,int r)
{
	if(set[id]) {do_reset(id,l,r);return;}
	if(reset[id]) {do_set(id,l,r);return;}
	rev[id]^=1;
	sum[id]=r-l+1-sum[id];
	swap(mmax[id],zmmax[id]);
	swap(lmax[id],zlmax[id]);
	swap(rmax[id],zrmax[id]);
	return;
}
void opt(int id,int l,int r,int type)
{
	if(type==0) do_reset(id,l,r);
	if(type==1) do_set(id,l,r);
	if(type==2) do_rev(id,l,r);
	return;
}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	
	sum[id]=sum[lson]+sum[rson];
	
	mmax[id]=max(mmax[lson],mmax[rson]);
	mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
	if(rmax[rson]==lenr) rmax[id]+=rmax[lson];

	zmmax[id]=max(zmmax[lson],zmmax[rson]);
	zmmax[id]=max(zmmax[id],zrmax[lson]+zlmax[rson]);
	zlmax[id]=zlmax[lson];
	zrmax[id]=zrmax[rson];
	if(zlmax[lson]==lenl) zlmax[id]+=zlmax[rson];
	if(zrmax[rson]==lenr) zrmax[id]+=zrmax[lson];
	return;
}
void pushdown(int id,int l,int r)
{
    int m=(l+r)/2;
	if(set[id]){do_set(lson,l,m);do_set(rson,m+1,r);set[id]=0;}
	if(reset[id]){do_reset(lson,l,m);do_reset(rson,m+1,r);reset[id]=0;}
	if(rev[id]){do_rev(lson,l,m);do_rev(rson,m+1,r);rev[id]=0;}
	return;
}
void build(int id,int l,int r)
{
	set[id]=reset[id]=rev[id]=0;
	if(l==r)
	{
		scanf("%d",&sum[id]);
		lmax[id]=rmax[id]=mmax[id]=sum[id];
		zmmax[id]=zlmax[id]=zrmax[id]=1-sum[id];
		return;
	}
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	pushup(id,l,r);
	return;
}
void update(int id,int l,int r,int L,int R,int type)
{
	if(L<=l && r<=R)
	{
		opt(id,l,r,type);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,type);
	if(R>m) update(rson,m+1,r,L,R,type);
	pushup(id,l,r);
	return;
}
int query_sum(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return sum[id];
	pushdown(id,l,r);
	int m=(l+r)/2,ret=0;
	if(L<=m) ret+=query_sum(lson,l,m,L,R);
	if(R>m) ret+=query_sum(rson,m+1,r,L,R);
	return ret;
}
int query_len(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return mmax[id];
	pushdown(id,l,r);
	int m=(l+r)/2,ret=0;
	if(L<=m) ret=max(ret,query_len(lson,l,m,L,R));
	if(R>m) ret=max(ret,query_len(rson,m+1,r,L,R));
	ret=max(ret,min(R,m+lmax[rson])-max(L,m+1-rmax[lson])+1);
	return ret;
}
int main()
{
	int i,j,t;
	int n,m;
	int op,a,b;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&op,&a,&b);a++;b++;
			if(op<=2) update(1,1,n,a,b,op);
			if(op==3) printf("%d\n",query_sum(1,1,n,a,b));
			if(op==4) printf("%d\n",query_len(1,1,n,a,b));
		}
	}
	return 0;
}

hdoj3308 LCIS

单点修改的最长连续递增子序列
比前面几题都要简单,但是磨蹭了n久。。原因是query的时候没弄清楚,query的时候可能去左子区间也可能去右子区间,还有一种是答案是左右子区间拼起来的,想是想到了,但是还是写错了。。这种情况下应该是左起点选max(L,m+1-rmax[lson]),右起点选min(R,m+lmax[rson]).但是我原来写的时候只有当L<=m+1-rmax[lson] && m+lmax[rson]<=R的时候才考虑这种情况。。。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
#define maxn 100000
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int data[maxn+10];
int lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	mmax[id]=max(mmax[lson],mmax[rson]);
	if(data[m]<data[m+1]) mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl && data[m]<data[m+1]) lmax[id]=lenl+lmax[rson];
	if(rmax[rson]==lenr && data[m]<data[m+1]) rmax[id]=lenr+rmax[lson];
	return;
}
void build(int id,int l,int r)
{
	if(l==r)
	{
		lmax[id]=rmax[id]=mmax[id]=1;
		scanf("%d",&data[l]);
		return;
	}
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	pushup(id,l,r);
	return;
}
void update(int id,int l,int r,int pos,int v)
{
	if(l==r)
	{
		data[l]=v;return;
	}
	int m=(l+r)/2;
	if(pos<=m) update(lson,l,m,pos,v);
	else update(rson,m+1,r,pos,v);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return mmax[id];
	int m=(l+r)/2,ret=0;
	if(L<=m) ret=query(lson,l,m,L,R);
	if(R>m) ret=max(ret,query(rson,m+1,r,L,R));
	if(data[m]<data[m+1])
		ret=max(ret,min(m+lmax[rson],R)-max(m+1-rmax[lson],L)+1);
    return ret;
}
void debug(int id,int l,int r)
{
    printf("l:%d  r:%d  mmax:%d\n",l,r,mmax[id]);
    if(l==r) return;
    int m=(l+r)/2;
    debug(lson,l,m);
    debug(rson,m+1,r);
    return;
}
int main()
{
    //freopen("data.in","r",stdin);
	int i,j,t;
	int n,m;
	int a,b;
	char com[3];
	scanf("%d",&t);
	while(t–)
	{
		scanf("%d%d",&n,&m);
		build(1,0,n-1);
		for(i=1;i<=m;i++)
		{
			scanf("%s%d%d",com,&a,&b);
			if(com[0]==’U') update(1,0,n-1,a,b);
			else printf("%d\n",query(1,0,n-1,a,b));
		}
	}
	return 0;
}

poj3667 Hotel

经典的区间合并的线段树
关于找满足要求长度的最左连续空闲区:
维护左起连续空闲区lmax,右起连续空闲区rmax,区间最长连续空闲区max。当区间max=len,若是则转入左子区间,否则看rmax[lson]+lmax[rson]是否>=len,若是,则直接返回m+1-rmax[lson],若还是不行,则忘右区间找一定能找到(因为已经确定max[id]>=len)。
为什么这样是正确的?
如果最终答案不是lmax那段,也不是rmax那段,而是当前区间中间的一段空白,那么如果它被两个子区间隔开,那么必然是rmax[lson]+lmax[rson],否则它必定在左子区间或右子区间,这种情况下会继续往下找。知道所求区间是lmax或rmax或rmax[lson]+lmax[rson]或到达叶子结点。所以只设置这些量是足够的。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=50000;
int lmax[maxn<<2],max[maxn<<2],rmax[maxn<<2];
bool set[maxn<<2],reset[maxn<<2];
int maxlen(int a,int b,int c)
{
	int ret=a;
	if(b>ret) ret=b;
	if(c>ret) ret=c;
	return ret;
}
void do_set(int id,int l,int r)
{
	lmax[id]=rmax[id]=max[id]=0;
	set[id]=1;reset[id]=0;
	return;
}
void do_reset(int id,int l,int r)
{
	int len=r-l+1;
	lmax[id]=rmax[id]=max[id]=len;
	reset[id]=1;set[id]=0;
	return;
}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]=lenl+lmax[rson];
	if(rmax[rson]==lenr) rmax[id]=lenr+rmax[lson];
	max[id]=maxlen(lmax[id],rmax[id],rmax[lson]+lmax[rson]);
	max[id]=maxlen(max[id],max[lson],max[rson]);
	return;
}
void pushdown(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	if(reset[id])
	{
		lmax[lson]=rmax[lson]=max[lson]=lenl;reset[lson]=1;set[lson]=0;
		lmax[rson]=rmax[rson]=max[rson]=lenr;reset[rson]=1;set[rson]=0;
		reset[id]=0;
	}
	if(set[id])
	{
		lmax[lson]=rmax[lson]=max[lson]=0;set[lson]=1;reset[lson]=0;
		lmax[rson]=rmax[rson]=max[rson]=0;set[rson]=1;reset[rson]=0;
		set[id]=0;
	}
	return;
}
void build(int id,int l,int r)
{
	set[id]=reset[id]=0;
	lmax[id]=rmax[id]=max[id]=r-l+1;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	return;
}
void update(int id,int l,int r,int L,int R,int type)
{
	if(L<=l && r<=R)
	{
		if(type==0) do_reset(id,l,r);
		else do_set(id,l,r);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,type);
	if(R>m) update(rson,m+1,r,L,R,type);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int len)
{
	if(max[id]<len) return 0;
	if(l==r) return l;
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(max[lson]>=len) return query(lson,l,m,len);
	if(rmax[lson]+lmax[rson]>=len) return m+1-rmax[lson];
	return query(rson,m+1,r,len);
}
void debug(int id,int l,int r)
{
	if(l==r)
	{
		printf("%d ",1-max[id]);return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	debug(lson,l,m);
	debug(rson,m+1,r);

}
int main()
{
	int i,j;
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			int c,a,b;
			scanf("%d",&c);
			if(c==1)
			{
				scanf("%d",&a);
				int pos=query(1,1,n,a);
				if(pos) update(1,1,n,pos,pos+a-1,1);
				printf("%d\n",pos);
				//debug(1,1,n);printf("\n");
				//printf("max[1]:%d\n",max[1]);
			}
			else
			{
				scanf("%d%d",&a,&b);
				update(1,1,n,a,a+b-1,0);
				//debug(1,1,n);printf("\n");
			}
		}
	}
	return 0;
}

poj2991 Crane——线段转化成向量,向量旋转

神奇的一道题,解法很奇妙————对我而言。。
题意:给出一些线段,起始时它们一次邻接的排列在二维笛卡尔坐标系上,端点分别是(0,w1)(0,w1+w2)……(0,w1+w1+……+wn),wi是第i个线段的长度。给出一些操作s,angle。表示把第s条线段的右端点p的后面的所有线段以p为中心旋转到p点两侧的线段成angle角度。(angle角度=以线段s以p点为中心逆时针转到与线段s+1重合经过的角度),要求每次操作后输出线段n右端点的坐标。
难点:直接做很麻烦,因为每次旋转的中心点可能不同,操作无法统一化表示,如果能统一化的话,就可以使用线段树了。
关键点:
1.把线段看成向量。
2.当进行操作是s,angle后,第s+1条线段开始的线段所在直线都旋转了angle角度。
3.向量(x1,y2)逆时针旋转a弧度后的端点坐标为
x1=x0*cos(a)-y0*sin(a);
y1=x0*sin(a)+y0*cos(a);
当顺时针旋转b弧度时,a=-b。相当与旋转了负角度。

有了这三个认识,题目就简单了。线段树中的结点(id,l,r)存储的是第l条线段的右端点到第r条线段的右端点表示的向量的右端点的横纵坐标。所以其实答案就是(x[1],y[1])。
那么怎样把题目告诉的旋转到成angle角度转化为旋转了多少角度呢?
这个简单,只要开个数组angle[],angle[i]表示第i条和第i+1条线段现在所成的角度。那么假如现在要旋转到成r弧度角,那么旋转了r-angle[i].注意化成弧度计算哦。

#include<stdio.h>
#include<string.h>
#include<math.h>
#define lson id<<1
#define rson id<<1|1
#define maxn 10000
const double eps=1e-8;
const double pi=acos((double)(-1.0));
double len[maxn+10],angle[maxn+10];
double x[maxn<<2],y[maxn<<2],rotate[maxn<<2];
double radio(double ang){return (ang*pi)/180;}
void change(double &x,double &y,double ang)
{
	double xx=x,yy=y;
	x=xx*cos(ang)-yy*sin(ang);
	y=xx*sin(ang)+yy*cos(ang);
	return;
}
void pushup(int id)
{
	x[id]=x[lson]+x[rson];
	y[id]=y[lson]+y[rson];
	return;
}
void pushdown(int id)
{
	if(fabs(rotate[id]-0)<eps) return;
	change(x[lson],y[lson],rotate[id]);rotate[lson]+=rotate[id];
	change(x[rson],y[rson],rotate[id]);rotate[rson]+=rotate[id];
	rotate[id]=0;
	return;
}
void build(int id,int l,int r)
{
	rotate[id]=0;
	if(l==r)
	{
		x[id]=0;y[id]=len[l];
		return;
	}
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	pushup(id);
	return;
}
void update(int id,int l,int r,int L,int R,double rad)
{
	if(L<=l && r<=R)
	{
		change(x[id],y[id],rad);
		rotate[id]+=rad;
		return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,rad);
	if(R>m) update(rson,m+1,r,L,R,rad);
	pushup(id);
	return;
}
int main()
{
	int i,j;
	int n,m;
	bool flag=1;
	while(~scanf("%d%d",&n,&m))
	{
		for(i=1;i<=n;i++) scanf("%lf",&len[i]);
		for(i=1;i<=n;i++) angle[i]=pi;
		int s;
		double ang;
		build(1,1,n);
		if(flag) flag=0;
		else printf("\n");
		for(i=1;i<=m;i++)
		{
			scanf("%d%lf",&s,&ang);
			double r=radio(ang)-angle[s];
			update(1,1,n,s+1,n,r);
			angle[s]=radio(ang);
			printf("%.2f %.2f\n",x[1],y[1]);
		}
	}
	return 0;
}

poj1436 Horizontally Visible Segments

终于ac了,不容易啊。。
题意:给出n条垂直的不相交线段,如果两条线段之间可以用一条不穿过其他线段的水平线段连接起来,那么称这两条线段互相可见。如果三条线段间两两可见,那么称这三条线段组成三角形,问总共有多少个三角形。
思路:每条线段的id(将线段按x坐标排序,id从1开始)作为颜色,用线段树维护区间的颜色。每次插入一条线段,就询问这段区间内有哪些颜色(也就是之前插入的哪些线段与当前线段互相可见),之后更新该区间的颜色。起始时整个区间颜色为0,当一段区间内有多种颜色时color设成-1。
注意一点:
| | |
| |
| | |
1 2 3
上图中x坐标=2的两条线段的y坐标分别为(1,2)(3,4),那么显然线段1和3是互相可见的,但是因为在线段树上插入线段3时[1,4]这个区间颜色全是2,所以会会认为线段3与1不是互相可见。这样就造成了漏数。
解决:方法是线段树的每个点乘2.这样x、x+1变成2x、2x+2,中间的2x+1这个点就可以表示区间(x,x+1).

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<set>
#include<vector>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=8000*2;
int color[maxn<<2];
bool lazy[maxn<<2];
typedef struct Seg{
	int x,y1,y2;
}Seg;
Seg seg[maxn/2+10];
set<int> s[maxn/2+10];
set<int>::iterator it;
vector<int> map[maxn/2+10];
int cur;
bool cmp(Seg a,Seg b){return a.x<b.x;}
void pushup(int id)
{
	if(color[lson]!=color[rson]) color[id]=-1;
	else color[id]=color[lson];
	return;
}
void pushdown(int id)
{
	if(!lazy[id] || color[id]==-1 || color[id]==0) return;
	lazy[id]=0;
	color[lson]=color[id];lazy[lson]=1;
	color[rson]=color[id];lazy[rson]=1;
	return;
}
void update(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
	{
        color[id]=cur;
		lazy[id]=1;
		return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R);
	if(R>m) update(rson,m+1,r,L,R);
	pushup(id);
	return;
}
void query(int id,int l,int r,int L,int R)
{
	if(color[id]==0) return;
	if(L<=l && r<=R && color[id]!=-1)
	{
		s[cur].insert(color[id]);
		return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) query(lson,l,m,L,R);
	if(R>m) query(rson,m+1,r,L,R);
	return;
}
int main()
{
	int t,n;
	int i,j,k;
	int x,y1,y2;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int maxd=-1;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&seg[i].y1,&seg[i].y2,&seg[i].x);
			seg[i].y1*=2;seg[i].y2*=2;
			if(seg[i].y2>maxd) maxd=seg[i].y2;
		}
		sort(seg+1,seg+1+n,cmp);
		for(i=1;i<=n;i++)
		{
			if(!s[i].empty()) s[i].clear();
			if(!map[i].empty()) map[i].clear();
		}
		memset(color,0,sizeof(color));
		memset(lazy,0,sizeof(lazy));
		for(i=1;i<=n;i++)
		{
			cur=i;
			query(1,0,maxn,seg[i].y1,seg[i].y2);
			update(1,0,maxn,seg[i].y1,seg[i].y2);
		}
		for(i=1;i<=n;i++)
		{
			for(it=s[i].begin();it!=s[i].end();it++)
				map[i].push_back(*it);
		}
		int ans=0;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<map[i].size();j++)
				for(k=j+1;k<map[i].size();k++)
				{
					int a=map[i][j],b=map[i][k];
					if(a>b) {a^=b;b^=a;a^=b;}
					if(s[b].find(a)!=s[b].end()) ans++;
				}
		}
		printf("%d\n",ans);
	}
	return 0;
}

poj3225 Help with Intervals——线段树

开始对于区间乘以2的方法没理解透彻导致错误。
由于涉及开闭区间,所以既要用到点又要用到区间。普通线段树实际上是将区间堪看成离散的点,每次操作都是对点进行操作,对连续的区间则无可奈何。
解决方法:对于数x,x乘2,2x表示点本身,2x+1表示(x,x+1)这段区间。这样问题就解决了。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=(65535<<1|1);
bool set[4*maxn],reset[4*maxn],rev[4*maxn];
int a[maxn+10];
void do_set(int id) {set[id]=1;reset[id]=rev[id]=0;}
void do_reset(int id) {reset[id]=1;set[id]=rev[id]=0;}
void do_rev(int id)
{
	if(set[id]==1) {do_reset(id);return;}
	if(reset[id]==1) {do_set(id);return;}
	rev[id]^=1;return;
}
void do_it(int id,int type)
{
	if(type==1) do_set(id);
	if(type==2) do_reset(id);
	if(type==3) do_rev(id);
}
void pushdown(int id)
{
	if(set[id]) {do_set(lson);do_set(rson);}
	if(reset[id]) {do_reset(lson);do_reset(rson);}
	if(rev[id]) {do_rev(lson);do_rev(rson);}
	set[id]=reset[id]=rev[id]=0;
}
void update(int id,int l,int r,int L,int R,int type)
{
    if(L>R || L<0) return;
	if(L<=l && r<=R)
	{
		do_it(id,type);return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,type);
	if(R>m) update(rson,m+1,r,L,R,type);
	return;
}
void out(int id,int l,int r)
{
	if(l==r)
	{
		if(set[id] || rev[id]) {a[l]=1;return;}
		if(reset[id]) {a[l]=0;return;}
		a[l]=0;return;
	}
	pushdown(id);
	int m=(l+r)/2;
	out(lson,l,m);
	out(rson,m+1,r);
}
int main()
{
	int i,j;
	char com[5],left,right;
	int l,r;
	memset(set,0,sizeof(set));
	memset(reset,0,sizeof(reset));
	memset(rev,0,sizeof(rev));
	while(~scanf("%s %c%d,%d%c",com,&left,&l,&r,&right))
	{
	    getchar();
		if(left=='[') l<<=1;
		else l=(l<<1|1);
		if(right==')') r=(r<<1)-1;
		else r=(r<<1);
		if(com[0]=='U') update(1,0,maxn,l,r,1);
		if(com[0]=='I') {update(1,0,maxn,0,l-1,2);update(1,0,maxn,r+1,maxn,2);}
		if(com[0]=='D') update(1,0,maxn,l,r,2);
		if(com[0]=='C') {update(1,0,maxn,0,l-1,2);update(1,0,maxn,r+1,maxn,2);update(1,0,maxn,l,r,3);}
		if(com[0]=='S') update(1,0,maxn,l,r,3);
	}
	out(1,0,maxn);
	bool flag=1;
	for(i=0;i<=maxn;i++)
	{
		if(((a[i]==1) && (i==0)) || ((a[i]==1) && (a[i-1]==0)))
		{
			if(!flag) printf(" ");
			else flag=0;
			if(i&1) printf("(%d,",i/2);
			else printf("[%d,",i/2);
		}
		if(((a[i]==1) && (i==maxn)) || ((a[i]==1) && (a[i+1]==0)))
		{
			if(i&1) printf("%d)",i/2+1);
			else printf("%d]",i/2);
		}
	}
	if(flag) printf("empty set");
	printf("\n");
	return 0;
}

hdoj3874 Necklace——线段树离线处理

好久没做题,刷下存在感。。
线段树题,问[l,r]之间数的和,同样的数只算一遍。
思路:把询问离线保存下来,按右端点排序,用hash[x]表示数x到目前为止出现的最右位置。如果x以前出现过,则把位置hash[x]处清零,然后当前位置置为x。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
#define maxn 50000+10
using namespace std;
typedef __int64 ll;
int n,m;
ll sum[4*maxn],ans[200000+10];
typedef struct Q{
	int l,r;
	int num;
}Q;
Q q[200000+10];
int hash[1000000+10];
void pushup(int id)
{
	sum[id]=sum[lson]+sum[rson];
	return;
}
void update(int id,int l,int r,int pos,ll v)
{
	if(l==r)
	{
		sum[id]=v;return;
	}
	int m=(l+r)/2;
	if(pos<=m) update(lson,l,m,pos,v);
	else update(rson,m+1,r,pos,v);
	pushup(id);
	return;
}
ll query(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return sum[id];
	int m=(l+r)/2;
	ll ret=0;
	if(L<=m) ret+=query(lson,l,m,L,R);
	if(R>m) ret+=query(rson,m+1,r,L,R);
	return ret;
}
bool cmp(Q a,Q b)
{
	return a.r<b.r;
}
bool cmp2(Q a,Q b)
{
	return a.num<b.num;
}
ll a[maxn];
int main()
{
	int i,j,k,t;
	scanf("%d",&t);
	while(t--)
	{
		memset(hash,0,sizeof(hash));
		memset(sum,0,sizeof(ll)*(4*n+5));
		scanf("%d",&n);//scanint(n);
		for(i=1;i<=n;i++) scanf("%I64d",&a[i]);//scanll(a[i]);
		scanf("%d",&m);//scanint(m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&q[i].l,&q[i].r);//scanint(q[i].l);scanint(q[i].r);
			q[i].num=i;
		}
		sort(q+1,q+1+m,cmp);
		k=0;
		for(i=1;i<=m;i++)
		{
			for(j=k+1;j<=q[i].r;j++)
			{
				if(!hash[a[j]])
				{
					hash[a[j]]=j;
					update(1,1,n,j,a[j]);
				}
				else
				{
					update(1,1,n,hash[a[j]],0);
					hash[a[j]]=j;
					update(1,1,n,j,a[j]);
				}
			}
			k=q[i].r;
			ans[q[i].num]=query(1,1,n,q[i].l,q[i].r);
		}
		for(i=1;i<=m;i++)
			printf("%I64d\n",ans[i]);
	}

	return 0;
}

cf371D Vessels

不知道哪错了,待改。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define lson id<<1
#define rson id<<1|1
typedef long long ll;
const int maxn=2e5+10;
ll a[4*maxn],sum[4*maxn];
bool lazy[4*maxn];
int n,m;
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];return;
}
void pushdown(int id)
{
    if(!lazy[id]) return;
    sum[lson]=0;lazy[lson]=1;
    sum[rson]=0;lazy[rson]=1;
    lazy[id]=0;
    return;
}
void build(int id,int l,int r)
{
    if(l==r)
    {
        scanf("%I64d",&a[id]);
        sum[id]=a[id];
        return;
    }
    int m=(l+r)/2;
    build(lson,l,m);
    build(rson,m+1,r);
    pushup(id);
    return;
}
void update(int id,int l,int r,int L,int R)
{
    if(L>R) return;
    if(L<=l && r<=R)
    {
        sum[id]=0;lazy[id]=1;
        return;
    }
    pushdown(id);
    int m=(l+r)/2;
    if(L<=m) update(lson,l,m,L,R);
    if(R>m) update(rson,m+1,r,L,R);
    pushup(id);
    return;
}
void update2(int id,int l,int r,int pos,ll v)
{
    if(l==r)
    {
        sum[id]-=v;
        if(sum[id]<0) sum[id]=0;
        return;
    }
    pushdown(id);
    int m=(l+r)/2;
    if(pos<=m) update2(lson,l,m,pos,v);
    else update2(rson,m+1,r,pos,v);
    pushup(id);
    return;
}
ll query_sum(int id,int l,int r,int L,int R)
{
    if(L>R) return 0;
    if(L<=l && r<=R)
    {
        return sum[id];
    }
    pushdown(id);
    int ret=0,m=(l+r)/2;
    if(L<=m) ret+=query_sum(lson,l,m,L,R);
    if(R>m) ret+=query_sum(rson,m+1,r,L,R);
    return ret;
}
ll query(int id,int l,int r,int pos)
{
    if(l==r)
    {
        return a[id]-sum[id];
    }
    pushdown(id);
    int m=(l+r)/2;
    if(pos<=m) return query(lson,l,m,pos);
    else return query(rson,m+1,r,pos);
}
int bsearch(int pos,int l,int r,ll v)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(query_sum(1,1,n,pos,mid)<v) l=mid+1;
        else r=mid-1;
    }
    return l;
}
void debug(int id,int l,int r)
{
    if(l==r)
    {
        printf("%d ",sum[id]);
        return;
    }
    int m=(l+r)/2;
    debug(lson,l,m);
    debug(rson,m+1,r);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        memset(lazy,0,sizeof(lazy));
        int com,p;
        ll x;
        build(1,1,n);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d",&com);
            if(com==1)
            {
                scanf("%d%I64d",&p,&x);
                int ret=bsearch(p,p,n,x);
                ll tmp=query_sum(1,1,n,p,ret-1);
                update(1,1,n,p,ret-1);
                update2(1,1,n,ret,x-tmp);
                //debug(1,1,n);puts("");
            }
            else
            {
                scanf("%d",&p);
                printf("%I64d\n",query(1,1,n,p));
                //debug(1,1,n);puts("");
            }
        }
    }
    return 0;
}