题目
BZOJ1018 [SHOI2008]堵塞的交通traffic
BZOJ2459: [BeiJing2011]神秘好人
这两道题思路相仿所以放在一起
1018 题解
沃日啊代码毒瘤啊（不过好像没有想像中毒瘤？），写了一天多。
主要思想就是用线段树每个节点维护区间边界的四个点的连通信息，然后合并就是跑一遍只有八个点的无向图获取便边界四个点连通性。注意这里维护的信息只是通过内部节点的边。
回答询问的时候需要询问三个区间(c1 < c2),，[c1,c2] [1,c1],[c2,n],注意可以从两边绕过去，不一定只用[c1,c2]区间的边，一共有两种情况，同行，不同行，判一下就行了。
之前用的G[4][4]表示连通性，每次up就跑一遍8个点的floyd，然后T了，我居然还没一眼看出来为什么，8^3不爆炸才怪，然后改成用6个变量直接维护就变成近似O(1)了？up的时候讨论一下是从中间哪条边过去的就行了。
应该有WA不止的同学吧。放一个datamaker，但是这个东西造大数据的时候很慢，因为方法拙劣无比，操作数2000就差不多要造1s了。不过造小数据才能手调嘛。
1018 题目代码
//QWsin
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x) for(int i=0;i<x;++i)
using namespace std;
const int maxn=100000+10;
const char msg[]={
'N','Y'};
inline int read()
{int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';return ret;
}int ok[maxn][2][2];//ok[i][j][k]表示i列j层往k方向连是否有边
// 0 * 1
//0...2 (4...6)
//1...3 (5...7)struct NodeG{int g01,g02,g03,g12,g13,g23,l,r;NodeG(int l=0,int r=0):l(l),r(r){g01=g02=g03=g12=g13=g23=0;}NodeG operator + (const NodeG &rhs)const{NodeG t(l,rhs.r);int t1=ok[r][1][1],t2=ok[r][2][1];if(g01 || (g02&&rhs.g01&&g13&&t1&&t2)) t.g01=1;if((g02&&t1&&rhs.g02)||(g03&&t2&&rhs.g12)) t.g02=1;if((g02&&t1&&rhs.g03)||(g03&&t2&&rhs.g13)) t.g03=1;if((g12&&t1&&rhs.g02)||(g13&&t2&&rhs.g12)) t.g12=1;if((g12&&t1&&rhs.g03)||(g13&&t2&&rhs.g13)) t.g13=1;if((g23&&rhs.g02&&rhs.g13&&t1&&t2) || rhs.g23) t.g23=1;return t;}
};#define mid ((l+r)>>1)
struct Node{NodeG g;//存放联通情况Node *lc,*rc;Node(int l,int r){lc=rc=NULL;g=NodeG(l,r);}inline void up(){g=lc->g+rc->g;}
}*root;void build(Node* &p,int l,int r){p=new Node(l,r); if(l==r) {p->g.g02=p->g.g13=1;return ;}//这两项是单列固定信息不会更改 build(p->lc,l,mid);build(p->rc,mid+1,r);p->up();
}//竖列更新信息(单点修改)
void updata1(Node *p,int l,int r,int pos,int val)
{if(l==r){p->g.g01=p->g.g23=val;p->g.g03=p->g.g12=val;return ;}if(pos<=mid) updata1(p->lc,l,mid,pos,val);else updata1(p->rc,mid+1,r,pos,val);p->up();
}
//找到加边后影响到的合并（即加边位置为它的mid的那个区间），从这里开始重新合并
void updata2(Node *p,int l,int r,int pos,int val)
{if(mid==pos) {p->up();return ;}if(mid > pos) updata2(p->lc,l,mid,pos,val);else updata2(p->rc,mid+1,r,pos,val);p->up();
}NodeG query(Node *p,int l,int r,int L,int R)
{if(L<=l&&r<=R) return p->g;if(R<=mid) return query(p->lc,l,mid,L,R);else if(mid<L) return query(p->rc,mid+1,r,L,R);else return query(p->lc,l,mid,L,R)+query(p->rc,mid+1,r,L,R);
}int t1[4][4],t2[4][4],t3[4][4];int n;
inline void query(int L,int R,int G[4][4])//复制一遍是因为按原来的邻接矩阵的方法，判断答案要方便一些，因为r1,c1,r2,c2都是变量
{NodeG t=query(root,1,n,L,R);G[0][1]=G[1][0]=t.g01;G[0][2]=G[2][0]=t.g02;G[0][3]=G[3][0]=t.g03;G[1][2]=G[2][1]=t.g12;G[1][3]=G[3][1]=t.g13;G[2][3]=G[3][2]=t.g23;
}char op[20];
//询问只通过内部的点是否能连通(r1,c1)~(r2,c2) int main()
{cin>>n;build(root,1,n);int r1,c1,r2,c2;while(1){scanf("%s",op);if(op[0]=='E') break;if(op[0]=='A') {r1=read();c1=read();r2=read();c2=read();if(c1>c2) swap(c1,c2),swap(r1,r2);if(r1==1&&c1==1&&r2==2&&c2==3){int stop=1; }if(r1==r2&&c1==c2) {
printf("Y\n");continue;}query(c1,c2,t1);query( 1,c1,t2);query(c2, n,t3);int ans=t1[r1-1][r2+1];if(r1==r2){
if(t2[2][3]&&t1[2-r1][4-r2]&&t3[0][1]) ans=1;}else{if(t2[2][3]&&t1[2-r1][1+r2]) ans=1;if(t3[0][1]&&t1[r1-1][4-r2]) ans=1;}putchar(msg[ans]);putchar('\n');}else{int val=op[0]=='O';r1=read();c1=read();r2=read();c2=read();if(r1==r2){if(c1>c2)swap(c1,c2);ok[c1][r1][1]=ok[c2][r1][0]=val;updata2(root,1,n,c1,val);}else updata1(root,1,n,c1,val);}}return 0;
}
1018 datamaker
//QWsin
#include<set>
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int n;struct Road{int r1,c1,r2,c2; Road(int r1,int c1,int r2,int c2):r1(r1),c1(c1),r2(r2),c2(c2){}bool operator < (const Road &rhs)const{if(r1!=rhs.r1) return r1<rhs.r1;if(c1!=rhs.c1) return c1<rhs.c1;if(r2!=rhs.r2) return r2<rhs.r2;return c2<rhs.c2;}inline void output(){printf("%d %d %d %d\n",r1,c1,r2,c2); }
};Road getRoad()
{int dir=rand()%2;if(dir){int r=rand()%2+1;int c=rand()%(n-1)+1;return Road(r,c,r,c+1);}else{int c=rand()%n+1;return Road(1,c,2,c);}
}set<Road>Roadset;int main()
{srand(time(0));n=rand()*rand()%3+2;//点数printf("%d\n",n);int Roadcnt=0;for(int i=1;i<=20;++i)//20是操作数{int kind=rand()%3;if(kind==0&&Roadcnt==3*n-2) continue;if(kind==1&&Roadcnt==0) continue;if(kind==0){printf("Open ");Road t=getRoad();while(Roadset.count(t)) t=getRoad();t.output();Roadset.insert(t);++Roadcnt;}else if(kind==1){printf("Close ");Road t=getRoad();while(!Roadset.count(t)) t=getRoad();t.output();Roadset.erase(t);--Roadcnt;}else{printf("Ask ");int r1=rand()%2+1,r2=rand()%2+1;int c1=rand()%n+1,c2=rand()%n+1;printf("%d %d %d %d\n",r1,c1,r2,c2);}}printf("Exit");return 0;
}
2459 题解
其实跟上道题差不多，但是莫名其妙调了很久，关键就在于对于每个询问考虑的情况还要多一些，局限于上一道题的方法，所以大数据一直WA。
这道题要问最短路所以非得用邻接矩阵然后跑floyd了。所以常数好像很大。
询问的时候要枚举完最短路出现的情况，要不然会GG。
2459 题目代码
//QWsin
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x) for(int i=0;i<x;++i)
using namespace std;
typedef long long ll;
const ll INF=1ll<<60;
const int maxn=100000+10;
const char msg[][10]={
"N","Y"};
inline int read()
{int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar())ret=ret*10+ch-'0';return ret;
}ll _G[8][8];
ll ok[maxn][3],w[maxn];
//ok[i][j]表示i列j层往右方连的边权
//w[i]表示第i列的边权 struct NodeG{ll G[4][4];int l,r;// 0 * 1//0...2 (4...6)//1...3 (5...7)NodeG(int l=0,int r=0):l(l),r(r){rep(i,4)rep(j,4)if(i!=j)G[i][j]=INF;else G[i][j]=0;}inline NodeG operator + (const NodeG &rhs)const{NodeG ret;rep(i,8) rep(j,8) _G[i][j]=INF;rep(i,4) rep(j,4){_G[i][j]=G[i][j];_G[i+4][j+4]=rhs.G[i][j];}_G[2][4]=_G[4][2]=ok[r][1];_G[3][5]=_G[5][3]=ok[r][2];rep(k,8) rep(i,8) rep(j,8)_G[i][j]= min(_G[i][j],_G[i][k] + _G[k][j]);ret.G[2][0]=ret.G[0][2]=_G[0][6];ret.G[3][0]=ret.G[0][3]=_G[0][7];ret.G[2][1]=ret.G[1][2]=_G[1][6];ret.G[3][1]=ret.G[1][3]=_G[1][7];ret.G[1][0]=ret.G[0][1]=_G[0][1];ret.G[3][2]=ret.G[2][3]=_G[6][7];ret.l=l;ret.r=rhs.r;return ret;}
};#define mid ((l+r)>>1)
struct Node{NodeG g;//存放联通情况Node *lc,*rc;Node(int l,int r){lc=rc=NULL;g=NodeG(l,r);}inline void up(){g=lc->g+rc->g;}
}*root;void build(Node* &p,int l,int r){p=new Node(l,r); if(l==r) {//这几项是单列固定信息p->g.G[0][1]=p->g.G[1][0]=w[l];p->g.G[2][3]=p->g.G[3][2]=w[l];p->g.G[0][2]=p->g.G[2][0]=0;p->g.G[0][3]=p->g.G[3][0]=w[l];p->g.G[1][2]=p->g.G[2][1]=w[l];p->g.G[1][3]=p->g.G[3][1]=0;return ;}build(p->lc,l,mid);build(p->rc,mid+1,r);p->up();
}//竖列更新信息
void updata1(Node *p,int l,int r,int pos)
{if(l==r){p->g.G[0][1]=p->g.G[1][0]=w[pos];p->g.G[2][3]=p->g.G[3][2]=w[pos];p->g.G[0][2]=p->g.G[2][0]=0;p->g.G[0][3]=p->g.G[3][0]=w[pos];p->g.G[1][2]=p->g.G[2][1]=w[pos];p->g.G[1][3]=p->g.G[3][1]=0;return ;}if(pos<=mid) updata1(p->lc,l,mid,pos);else updata1(p->rc,mid+1,r,pos);p->up();
}void updata2(Node *p,int l,int r,int pos)
{if(mid==pos) {p->up();return ;}if(mid > pos) updata2(p->lc,l,mid,pos);else updata2(p->rc,mid+1,r,pos);p->up();
}NodeG query(Node *p,int l,int r,int L,int R)
{if(L<=l&&r<=R) return p->g;if(R<=mid) return query(p->lc,l,mid,L,R);else if(mid<L) return query(p->rc,mid+1,r,L,R);else return query(p->lc,l,mid,L,R)+query(p->rc,mid+1,r,L,R);
}int n;int main()
{cin>>n;for(int i=1;i<n;++i) ok[i][1]=read();for(int i=1;i<=n;++i) w[i]=read();for(int i=1;i<n;++i) ok[i][2]=read();build(root,1,n);int op,a,b,c;int m;cin>>m;while(m--){op=read();if(!op){a=read();b=read();c=read();if(a==1){w[b]=c;updata1(root,1,n,b);}else {ok[b][a?2:1]=c;updata2(root,1,n,b);}}else{a=read();b=read();int r1=((a&1)^1)+1,c1=(a-1)/2+1,r2=((b&1)^1)+1,c2=(b-1)/2+1;if(r1==r2&&c1==c2) {
printf("0\n");continue;}if(c1>c2) swap(c1,c2),swap(r1,r2);NodeG t1=query(root,1,n,c1,c2);NodeG t2=query(root,1,n,1,c1);NodeG t3=query(root,1,n,c2,n);ll ans=t1.G[r1-1][1+r2];if(r1==r2){ans=min(ans,t2.G[2][3]+t1.G[2-r1][4-r1]+t3.G[1][0]); ans=min(ans,t1.G[r1-1][4-r2]+t3.G[0][1]);ans=min(ans,t1.G[r2+1][2-r1]+t2.G[2][3]);}else {ans=min(ans,t3.G[0][1]+t1.G[2-r1][4-r2]+t2.G[2][3]);ans=min(ans,t2.G[2][3]+t1.G[2-r1][r2+1]);ans=min(ans,t3.G[0][1]+t1.G[r1-1][4-r2]);}printf("%lld\n",ans);}}return 0;
}2459 datamaker
//QWsin
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MOD=10000;//边权范围
int main()
{int n=100000;//长度srand(time(0));printf("%d\n",n);for(int i=1;i<n;++i) printf("%d ",rand()%MOD+1);putchar('\n');for(int i=1;i<=n;++i) printf("%d ",rand()%MOD+1);putchar('\n');for(int i=1;i<n;++i) printf("%d ",rand()%MOD+1);putchar('\n');puts("");int m=100000;//操作数printf("%d\n",m);while(m--){int op=rand()%2;if(!op){printf("1 %d %d\n",rand()%(2*n)+1,rand()%(2*n)+1);}else {int k=rand()%3;printf("0 %d ",k);if(k==0||k==2) printf("%d ",rand()%(n-1)+1);else printf("%d ",rand()%n+1);printf("%d\n",rand()%MOD+1);}}return 0;
}