栈都做了些什么？

当一个数列经过一个栈的时候，经由它独特的入栈和出栈操作，这个数列会发生些什么？抛开具体的数值，对于一数列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

Advertisements

Poj 3277

一开始以为这道题不需要传递参数，后来发现我错了..比如，先插入线段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;
 }

poj 2763

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

通过巧妙地利用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;
}