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