标签存档：数据结构

【题目大意】
给出一些只在端点相交的线段。
问在连了第几条边之后，这些线段中的一部分连成了一个完整的封闭图形。
【算法分析】
封闭图形就是一个环，如果已经成同一连通分量的两个点再被连，就是成环了。
这个可以用并差集判断。
然后我们需要快速查找点。
由于本题都是静态的东西，所以快排+二分足矣。
如果需要动态算法可以考虑hash表和平衡树。
【其它】1A
【CODE】

#include #include #include struct Point{int x,y;}list[400005],a[200005][2];
int n,tot,f[400005];

void input(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d%d%d",&a[i][0].x,&a[i][0].y,&a[i][1].x,&a[i][1].y);
list[++tot]=a[i][0];
list[++tot]=a[i][1];
}
}

int Findst(int x){
int l=1,r=tot,mid;
while (l mid=(l+r)/2;
if (x>list[mid].x) l=mid+1;
else r=mid;
}
return l;
}

int Finded(int x){
int l=1,r=tot,mid;
while (l+1 mid=(l+r)/2;
if (x>=list[mid].x) l=mid;
else r=mid-1;
}
if (x==list[r].x) return r;
return l;
}

int Find(Point tmp){
int l=Findst(tmp.x),r=Finded(tmp.x),mid;
while (l mid=(l+r)/2;
if (tmp.y>list[mid].y) l=mid+1;
else r=mid;
}
return l;
}

int cmp(const void *x,const void *y){
if (((Point*)x)->x==((Point*)y)->x) return ((Point*)x)->y-((Point*)y)->y;
return ((Point*)x)->x-((Point*)y)->x;
}

int GF(int p){
if (f[p]==p) return p;
return f[p]=GF(f[p]);
}

void solve(){
for (int i=1;i<=tot;i++) f[i]=i;
for (int x,y,i=1;i<=n;i++){
x=Find(a[i][0]);
y=Find(a[i][1]);
if (GF(x)==GF(y)){
printf("%dn",i);
return;
}
f[f[x]]=f[y];
}
printf("0n");
}

int main(){
input();
qsort(list+1,tot,sizeof(Point),cmp);
solve();
}

【题目地址】https://www.spoj.pl/problems/QTREE3/

【题目大意】
给定一棵树，一开始所有点都是白色的。
给定两个操作：
0 x：把点x变色（本来是白色变成黑色，本来是黑色变成白色）
1 x：求从结点1到点x的路径上，第一个黑色的点是哪一个？如果没有，输出-1。
【算法分析】
树链剖分例题(比本文详细)：http://hi.baidu.com/edwardmj/blog/item/2894235220a1be501038c2c9.html
首先显然把结点1当做根变成有根树。
轻重边剖分，然后都于每个重路径建立一棵线段树，然后对于操作0，就把线段树里对应那个点取反即可。
然后对于操作1，就从点x一直向父亲走，遇到重路径就跳到重路径的起始端，并用线段树取最小值，遇到轻边的话就直接走。
【其它】
跑了12s+。。。。果然我写的程序总是比较慢= =
【CODE】
#include #include #include const int N=100005;
const int INF=1000000000;
struct gtp{int x,y,next,op,inlist;}g[N*2];
struct TT{int l,r,zz;}tr[N*8];
int n,m,e,times,tot,ct,ans;
int ls[N],list[N],fa[N],Size[N],myheavy[N],black[N];
int color[N],cst[N];

void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
g[++e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}

void input(){
scanf("%d%d",&n,&m);
for (int i=1,x,y;i scanf("%d%d",&x,&y);
addedge(x,y);
}
}

void predfs(int p){
Size[p]=times++;
for (int t=ls[p];t;t=g[t].next)
if (!fa[p] || t!=g[fa[p]].op){
fa[g[t].y]=t;
predfs(g[t].y);
}
Size[p]=times-Size[p];
}

void dfs(int p){
int mt,mm=-INF;
for (int t=ls[p];t;t=g[t].next)
if ((!fa[p] || t!=g[fa[p]].op) && Size[g[t].y]>mm){
mm=Size[g[t].y];
mt=t;
}
if (mm==-INF) return;
myheavy[p]=mt;
list[++tot]=mt;
g[mt].inlist=tot;
dfs(g[mt].y);
for (int t=ls[p];t;t=g[t].next)
if ((!fa[p] || t!=g[fa[p]].op) && t!=mt)
dfs(g[t].y);
}

void draw_color(){
ct=color[1]=cst[1]=1;
for (int i=2;i<=tot;i++){
if (g[list[i-1]].y!=g[list[i]].x) cst[++ct]=i;
color[i]=ct;
}
}

void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r; tr[p].zz=0;
if (l==r) return;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}

void change(int p,int x){
if (tr[p].l==tr[p].r){
if (tr[p].zz) tr[p].zz=0;
else tr[p].zz=g[list[x]].x;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (x<=mid) change(p*2,x);
else change(p*2+1,x);
if (tr[p*2].zz) tr[p].zz=tr[p*2].zz;
else tr[p].zz=tr[p*2+1].zz;
}

void Get_zz(int p,int l,int r){
if (l<=tr[p].l && tr[p].r<=r){
if (tr[p].zz) ans=tr[p].zz;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (r>mid) Get_zz(p*2+1,l,r);
if (l<=mid) Get_zz(p*2,l,r);
}

void Try(int x){
if (black[x]) ans=x;
if (x==1) return;
if (!g[fa[x]].inlist) Try(g[fa[x]].x);
else{
Get_zz(1,cst[color[g[fa[x]].inlist]],g[fa[x]].inlist);
Try(g[list[cst[color[g[fa[x]].inlist]]]].x);
}
}

void deal(){
for (int op,x,i=1;i<=m;i++){
scanf("%d%d",&op,&x);
if (op==0){
black[x]^=1;
if (myheavy[x]) change(1,g[myheavy[x]].inlist);
}else{
ans=0;
Try(x);
if (ans) printf("%dn",ans);
else printf("-1n");
}
}
}

int main(){
input();
predfs(1);
dfs(1);
draw_color();
build(1,1,tot);
deal();
}

【题目大意】
给出一棵带权的树。有两种询问。
1、问节点a到结点b路径的权和。
2、问节点a到结点b路径中第k个点是哪个。
【算法分析】
直接搞个RMQ来算LCA。
对于询问1，轻松得出ans=dist[a]+dist[b]-dist[LCA(a,b)]
对于询问2，按照a和b到LCA(a,b)的距离，可以判断他在LCA到a的链上还是到b的链上。
进一步转化为询问(x,y)：x上根走y步到达哪一个节点。
我们先把询问都放进链表里，然后一次记录路径的DFS，轻松解决。
【其他】1A
【CODE】
#include #include #include const int N=10005;
const int QQ=1000000;
struct edge{int y,w;edge *next;}space[N*2],*ls[N],Qspace[QQ],*Qls[N];
int n,e,Tc,Qe,tot,Qn;
int dist[N],dep[N],list[N*2],R[N],ans[QQ];
int rmq_node[17][N*2],rmq_dep[17][N*2],lg[N*2];

void addedge(int x,int y,int w){
space[++e].y=y; space[e].w=w;
space[e].next=ls[x]; ls[x]=&space[e];
}

void predfs(int p,int fa){
list[++tot]=p;
R[p]=tot;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa){
dist[t->y]=dist[p]+t->w;
dep[t->y]=dep[p]+1;
predfs(t->y,p);
list[++tot]=p;
}
}

void buildrmq(){
for (int i=1;i<=tot;i++){
rmq_node[0][i]=list[i];
rmq_dep[0][i]=dep[list[i]];
}
for (int k=1;1< for (int i=1;i+(1< if (rmq_dep[k-1][i] rmq_dep[k][i]=rmq_dep[k-1][i];
rmq_node[k][i]=rmq_node[k-1][i];
}else{
rmq_dep[k][i]=rmq_dep[k-1][i+(1< rmq_node[k][i]=rmq_node[k-1][i+(1< }
}

void init(){
e=0; memset(ls,0,sizeof(ls));
Qn=0; Qe=0; memset(Qls,0,sizeof(Qls));
scanf("%d",&n);
for (int i=1,x,y,w;i scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);
addedge(y,x,w);
}
dist[1]=0; dep[1]=0; tot=0;
predfs(1,0);
buildrmq();
}

void addquestion(int x,int y){
Qspace[++Qe].y=y; Qspace[Qe].next=Qls[x]; Qls[x]=&Qspace[Qe];
Qspace[Qe].w=Qn;
}

int LCA(int l,int r){
if (l>r){
int tmp=l; l=r; r=tmp;
}
int k=lg[r-l+1];
if (rmq_dep[k][l] return rmq_node[k][l];
else
return rmq_node[k][r-(1<}

void build_question(){
char op[100];
int x,y,k,p;
for (Qn=1;;Qn++){
scanf("%s",op+1);
if (op[1]==’D’ && op[2]==’O’){
Qn–;
break;
}
if (op[1]==’D’){
scanf("%d%d",&x,&y);
p=LCA(R[x],R[y]);
ans[Qn]=dist[x]-2*dist[p]+dist[y];
}
else{
scanf("%d%d%d",&x,&y,&k);
p=LCA(R[x],R[y]);
if (dep[x]-dep[p]+1==k) ans[Qn]=p;
else if (k else addquestion(y,dep[y]-dep[p]-(k-(dep[x]-dep[p]+1)));
}
}
}

void solve(int p,int fa){
list[++tot]=p;
for (edge *q=Qls[p];q;q=q->next)
ans[q->w]=list[tot-q->y];
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa) solve(t->y,p);
tot–;
}

int main(){
lg[1]=0;
for (int i=2;i lg[i]=lg[i-1];
if (1< }
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
init();
build_question();
tot=0;
solve(1,0);
for (int j=1;j<=Qn;j++) printf("%dn",ans[j]);
}
}

【题目】

Description

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？

Input

输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目
第二行包括n个数，表示序列的初始状态
接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b

Output

对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

Sample Input

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

Sample Output

5
2
6
5

Hint

对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000 【算法分析】
就是线段树。但是注意标记下传的函数要写好，下传覆盖为0或覆盖为1的标记的时候，需要把儿子原本的标记都删掉（因为之前的标记在这个覆盖后都没有用了）。
然后处理标记就先搞覆盖，再弄翻转。因为如果是覆盖操作在后的话，那么所有标记都会消失，而现在标记共存的话，肯定是先覆盖再翻转。注意了这一点以后就很容易AC了。
【CODE】
#include #include #include #include using namespace std;
const int N=100005;
int n,m;
int a[N];
struct Treetype{
struct Node{int l,r,FL0,FL1,FR0,FR1,N0,N1,L0,L1,c0,c1,filp;}tr[N*5];

void pushdown(int pos){
Node &p=tr[pos];
if (p.c0){
p.FL0=p.FR0=p.N0=p.L0=p.r-p.l+1;
p.FL1=p.FR1=p.N1=p.L1=0;
p.c0=0;
if (p.l!=p.r){
tr[pos*2].c0=1;
tr[pos*2].c1=0;
tr[pos*2].filp=0;
tr[pos*2+1].c0=1;
tr[pos*2+1].c1=0;
tr[pos*2+1].filp=0;
}
}
if (p.c1){
p.FL0=p.FR0=p.N0=p.L0=0;
p.FL1=p.FR1=p.N1=p.L1=p.r-p.l+1;
p.c1=0;
if (p.l!=p.r){
tr[pos*2].c1=1;
tr[pos*2].c0=0;
tr[pos*2].filp=0;
tr[pos*2+1].c1=1;
tr[pos*2+1].c0=0;
tr[pos*2+1].filp=0;
}
}
if (p.filp){
swap(p.FL0,p.FL1);
swap(p.FR0,p.FR1);
swap(p.N0,p.N1);
swap(p.L0,p.L1);
if (p.l!=p.r){
tr[pos*2].filp^=1;
tr[pos*2+1].filp^=1;
}
p.filp=0;
}
}

void update(int pos){
Node &p=tr[pos];
pushdown(pos);
if (p.l!=p.r){
pushdown(pos*2);
pushdown(pos*2+1);
}
if (p.l==p.r) return;
Node &L=tr[pos*2],&R=tr[pos*2+1];
p.N0=L.N0+R.N0;
p.N1=L.N1+R.N1;
p.L0=max(L.L0,R.L0); p.L0=max(p.L0,L.FR0+R.FL0);
p.L1=max(L.L1,R.L1); p.L1=max(p.L1,L.FR1+R.FL1);
p.FL0=L.FL0; if (L.FL0==L.r-L.l+1) p.FL0+=R.FL0;
p.FL1=L.FL1; if (L.FL1==L.r-L.l+1) p.FL1+=R.FL1;
p.FR0=R.FR0; if (R.FR0==R.r-R.l+1) p.FR0+=L.FR0;
p.FR1=R.FR1; if (R.FR1==R.r-R.l+1) p.FR1+=L.FR1;
}

void build(int pos,int l,int r){
Node &p=tr[pos];
p.l=l; p.r=r; p.c0=p.c1=p.filp=0;
if (l==r){
if (a[l]){
p.FL0=p.FR0=p.N0=p.L0=0;
p.FL1=p.FR1=p.N1=p.L1=1;
}
else{
p.FL0=p.FR0=p.N0=p.L0=1;
p.FL1=p.FR1=p.N1=p.L1=0;
}
return;
}
int mid=(l+r)/2;
build(pos*2,l,mid);
build(pos*2+1,mid+1,r);
update(pos);
}

void ins(int pos,int l,int r,int op){
Node &p=tr[pos];
if (r update(pos);
if (l<=p.l && p.r<=r){
switch (op){
case 0:p.c0=1; break;
case 1:p.c1=1; break;
case 2:if (p.filp) for (;;); p.filp^=1; break;
}
update(pos);
return;
}
ins(pos*2,l,r,op);
ins(pos*2+1,l,r,op);
update(pos);
}

void solve3(int pos,int l,int r,int &ans){
Node &p=tr[pos];
if (r update(pos);
if (l<=p.l && p.r<=r){
ans+=p.N1;
return;
}
solve3(pos*2,l,r,ans);
solve3(pos*2+1,l,r,ans);
}

void solve4(int pos,int l,int r,int &rr,int &ans){
Node &p=tr[pos];
if (r update(pos);
if (l<=p.l && p.r<=r){
ans=max(ans,p.L1);
ans=max(ans,rr+p.FL1);
if (p.L1==p.r-p.l+1) rr+=p.L1;
else rr=p.FR1;
ans=max(ans,rr);
return;
}
solve4(pos*2,l,r,rr,ans);
solve4(pos*2+1,l,r,rr,ans);
}
}Tree;

int main(){
freopen("operation.in","r",stdin);
freopen("operation.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
Tree.build(1,1,n);
for (int i=1;i<=m;i++){
int x,y,op;
scanf("%d%d%d",&op,&x,&y);
x++; y++;
if (op<=2) Tree.ins(1,x,y,op);
if (op==3){
int ans=0;
Tree.solve3(1,x,y,ans);
printf("%dn",ans);
}
if (op==4){
int tmp=0,ans=0;
Tree.solve4(1,x,y,tmp,ans);
printf("%dn",ans);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}

【算法分析】
维护4个域：
fl:最左边的点是否在原位，
fr:最右边的点是否在原位，
c:这条线段被压下多少次
sum:这条线段上有多少个连续部分。
然后维护即可。
要注意到题目中一个很重要的条件：
r i j means the pressure acting on blocks from number i to j is released. i and j is always the effective range of an existing pressure (inclusive, 0 <= i <= j < n).
【CODE】
#include #include #include #include using namespace std;
const int N=200005;
int n,tot,LEN;
int xl[N];
struct opnode{int l,r,t;}op[N];
struct node{int l,r,fl,fr,c,sum;}tr[N*4];

int Find(int x){
int l=1,r=tot,mid;
while (l mid=(l+r)/2;
if (x>xl[mid]) l=mid+1;
else r=mid;
}
return l;
}

void input(){
cin >> LEN >> n;
char type;
for (int i=1;i<=n;i++){
type=getchar();
while (type==’ ‘ || type==’n’) type=getchar();
scanf("%d%d",&op[i].l,&op[i].r);
if (type==’p’) op[i].t=1;
else op[i].t=0;
}

tot=0;
for (int i=1;i<=n;i++){
xl[++tot]=op[i].l;
xl[++tot]=op[i].r;
if (op[i].l>0) xl[++tot]=op[i].l-1;
xl[++tot]=op[i].l+1;
xl[++tot]=op[i].r-1;
if (op[i].r }
sort(xl+1,xl+tot+1);
int nt=0;
for (int i=1;i<=tot;i++)
if (!nt || xl[i]!=xl[nt])
xl[++nt]=xl[i];
tot=nt;
for (int i=1;i<=n;i++){
op[i].l=Find(op[i].l);
op[i].r=Find(op[i].r);
}
}

void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r; tr[p].fl=tr[p].fr=1; tr[p].c=0; tr[p].sum=1;
if (l==r) return;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}

void update(int p){
if (tr[p].c) return;
tr[p].sum=tr[p*2].sum+tr[p*2+1].sum;
if (tr[p*2].fr && tr[p*2+1].fl) tr[p].sum–;
tr[p].fl=tr[p*2].fl; tr[p].fr=tr[p*2+1].fr;
}

void ins(int p,int l,int r){
if (r if (l<=tr[p].l && tr[p].r<=r){
tr[p].c++;
tr[p].sum=tr[p].fl=tr[p].fr=0;
return;
}
ins(p*2,l,r);
ins(p*2+1,l,r);
update(p);
}

void del(int p,int l,int r){
if (r if (l<=tr[p].l && tr[p].r<=r){
tr[p].c–;
if (!tr[p].c)
if (tr[p].l==tr[p].r) {tr[p].sum=tr[p].fl=tr[p].fr=1;}
else update(p);
return;
}
del(p*2,l,r);
del(p*2+1,l,r);
update(p);
}

int main(){
int Tc;
cin >> Tc;
for (int k=1;k<=Tc;k++){
printf("Case #%d:n",k);
input();
build(1,1,tot);
for (int i=1;i<=n;i++){
if (op[i].t) ins(1,op[i].l,op[i].r);
else del(1,op[i].l,op[i].r);
printf("%dn",tr[1].sum);
}
}
}