Archive

Posts Tagged ‘数据结构’

栈都做了些什么?

October 27, 2010 Leave a comment

当一个数列经过一个栈的时候,经由它独特的入栈和出栈操作,这个数列会发生些什么?抛开具体的数值,对于一数列1, 2, 3, … , n, 将它以不同的方式,经过完整的入栈和出栈操作,可以得到哪些数列?

我们来考察一个较为简单的序列1, 2, 3, 4, 5

以及两个待考察的结果:

1, 2, 4, 5, 3

1, 2, 5, 3, 4

很明显,第一个序列是可得到的。我们依次将1入栈,1出栈,2入栈,2出栈, 3, 4入栈,4出栈, 5入栈, 5出栈就可得到该数列。

然而,第二个是不可能的。前两个元素都没有问题。为了第三个弹出5,我们需要先将3,4入栈,此时下一个出栈的只能是4,而该数列中却弹出了3,故不可能。

那么,一般地,如何判断一个数列是否是满足条件的呢?

可以观察到,每一个数列可以划分为若干段单调递增的子数列,比如第一个:1245|3,第二个:125|34

事实上,一个数列满足条件,当且仅当在它每两段单调递增的子数列的交界处,满足后一个数列的第一个数是之前没有出现过的数中最大的

证明也并不困难,事实上,同时在这个栈中的元素一定满足从栈底到栈顶单调递增,那么在这个交界处(也就是开始往外弹积存已久的数了)必定先弹出栈顶较大的元素;另一方面,我们也很容易根据单调递增子数列的分段方法,构造出一种具体的入栈出栈次序。

这样,我们就可以很快知道,下面几个数列都不能由1, 2, 3, …, 9经栈操作得到

1, 3, 2, 5, 4, 8, 6, 7, 9 –> 13|25|48|679

3, 2, 1, 5, 7, 4, 6, 8, 9 –> 3|2|157|4689

Categories: OI Tags: , , ,

Poj 3277

July 29, 2010 Leave a comment

一开始以为这道题不需要传递参数,后来发现我错了..比如,先插入线段12 40 11,再插入13 40 13,若不传递参数,那么12~13这一段就会被无视

范围很大,要离散化;注意结果可能超int;区间划分时要注意

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXN 100001 #define MAXP 200001 #define MAXT 400001 struct segment{     int x,y,h; } seg[MAXN]; struct Point{     int x,id1,id2; } point[MAXP]; int N,pnum,tot; long long area[MAXT],height[MAXT],change[MAXP]; int cmp(const void *a, const void *b){     segment *x=(segment*)a, *y=(segment*)b;     return x->h-y->h; } int cmp1(const void *a, const void *b){     Point *x=(Point*)a, *y=(Point*)b;     return x->x-y->x; } void add(int p, int l, int r, int x, int y, int h){     if(l==x&&r==y||r-l<=1){         height[p]=h;         area[p]=(change[y]-change[x])*h;         return;     }     int m=l+r>>1;     if(height[p]){         height[p*2]=height[p*2+1]=height[p];         area[p*2]=(change[m]-change[l])*height[p];         area[p*2+1]=(change[r]-change[m])*height[p];     }     height[p]=0;     if(y<=m){         add(p*2,l,m,x,y,h);     }else if(x>=m){         add(p*2+1,m,r,x,y,h);     }else{         add(p*2,l,m,x,m,h);         add(p*2+1,m,r,m,y,h);     }     area[p]=area[p*2]+area[p*2+1]; } int main(){     scanf("%d\n",&N);     for(int i=1;i<=N;++i){         scanf("%d %d %d\n",&seg[i].x,&seg[i].y,&seg[i].h);         point[++pnum].x=seg[i].x;         point[pnum].id1=i;         point[pnum].id2=1;         point[++pnum].x=seg[i].y;         point[pnum].id1=i;         point[pnum].id2=2;     }     qsort(point+1,pnum,sizeof(point[0]),cmp1);     for(int i=1;i<=pnum;++i){         if(point[i].x!=point[i-1].x){             ++tot;             change[tot]=point[i].x;         }         if(point[i].id2==1){             seg[point[i].id1].x=tot;         }else{             seg[point[i].id1].y=tot;         }     }     qsort(seg+1,N,sizeof(seg[0]),cmp);     for(int i=1;i<=N;++i){         add(1,1,tot,seg[i].x,seg[i].y,seg[i].h);     }     printf("%lld\n",area[1]);     return 0; }
Categories: OI Tags: , , , ,

poj 2763

July 27, 2010 Leave a comment

这题要求两个操作:求树上两个顶点的距离,以及改变某条边的权值。

通过巧妙地利用DFS序列和树状数组,我们可以在O(lg n)时间内完成每个操作。

比如对于一个有8个顶点,且边集如下的树:

1 2

1 3

1 4

2 5

2 6

4 7

7 8

它的DFS序列为 1 2 5 6 3 4 7 8

对于某条树上的边,我们将边指向的子结点的权值加上边的权值,再将这棵子树之后的第一个结点的权值减去这条边的权值,那么就可以用一个树状数组维护每个结点到根结点的距离。

比如 连接1和2的这条边权值为3,我们在2上加3,在3上减3即可。这样修改边权也非常方便。

两个结点间距离:dis(a)+dis(b)-2*dis(LCA(Tree,a,b))

拿这题来复习树状数组,RMQ,LCA…

要注意几个情况

RE一般是数组没开够 开大点..

TLE可能是算法没优化好 实在不行试试用getchar输入加速

WA原因很多,要注意结点到自身的LCA

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXN 222222
struct Edge{
	int v,w;
	Edge *next;
} *edge[MAXN], mempool[MAXN];
int memnum, road[MAXN][3], dep[MAXN], vis[MAXN], tapp[MAXN],
stack[MAXN], app[MAXN], snum, tnum, n, q, cur, tree[MAXN],
son[MAXN], cnum[MAXN], st[MAXN][20];
inline int rmin(int a, int b){
	return dep[a]<dep[b]?a:b;
}
void add(int u, int v, int w){
	Edge *e=&mempool[memnum++];
	e->v=v,e->w=w,e->next=edge[u],edge[u]=e;
}
int getn(){
	char ch;
	int res=0;
	for(ch=getchar();'0'<=ch&&ch<='9';ch=getchar())
		res=res*10+ch-'0';
	return res;
}
void predfs(int now, int deep){
	dep[now]=deep;
	vis[now]=1;
	stack[++snum]=now;
	tree[++tnum]=now;
	tapp[now]=tnum;
	if(!app[now]) app[now]=snum;
	for(Edge *tmp=edge[now];tmp;tmp=tmp->next){
		if(!vis[tmp->v]){
			predfs(tmp->v,deep+1);
			stack[++snum]=now;
			son[now]+=son[tmp->v]+1;
		}
	}
}
void find(int i, int k){
	if(k==0){
		st[i][k]=stack[i];
		return;
	}
	if(!st[i][k-1]) find(i,k-1);
	if(!st[i+(1<<(k-1))][k-1]) find(i+(1<<(k-1)),k-1);
	st[i][k]=rmin(st[i][k-1],st[i+(1<<(k-1))][k-1]);
}
int rmq(int l, int r){
	int k=int(log(1.0*(r-l+1))/log(2.0)),kr=r-(1<<k)+1;
	if(!st[l][k]) find(l,k);
	if(!st[kr][k]) find(kr,k);
	return rmin(st[l][k], st[kr][k]);
}
int getsum(int x){
	int res=0;
	for(;x>0;x-=x&-x)
		res+=cnum[x];
	return res;
}
void add(int x, int d){
	for(;x<=n;x+=x&-x)
		cnum[x]+=d;
}
int lca(int a, int b){
	if(a==b) return a;
	int x=app[a], y=app[b];
	if(x<y) return rmq(x,y);
	else return rmq(y,x);
}
int dist(int now){
	return getsum(tapp[now]);
}
int ask(int a, int b){
	return dist(a)+dist(b)-2*dist(lca(a,b));
}
void change(int i, int w){
	int a=road[i][0], b=road[i][1];
	if(dep[a]>dep[b]){int tmp=a;a=b;b=tmp;}
	add(tapp[b], w-road[i][2]);
	add(tapp[b]+son[b]+1, road[i][2]-w);
	road[i][2]=w;
}
int main(){
	int u,a,b,w,c;
	scanf("%d %d %d\n",&n,&q,&cur);
	for(int i=1;i<n;++i){
		a=getn(), b=getn(), w=getn();
		add(a,b,w);
		add(b,a,w);
		road[i][0]=a;
		road[i][1]=b;
		road[i][2]=w;
	}
	predfs(1,0);
	for(int i=1;i<n;++i){
		w=road[i][2];
		road[i][2]=0;
		change(i,w);
	}
	for(int i=1;i<=q;++i){
		c=getn();
		if(!c){
			u=getn();
			printf("%d\n",ask(cur,u));
			cur=u;
		}else{
			a=getn(), b=getn();
			change(a,b);
		}
	}
	return 0;
}
Categories: OI Tags: , , , , ,