P12704 Retribution

我也不知道為什么能過做法。

考慮暴力縮點，然后做線段樹合并。

細節上，由于要在可持久化線段樹上合并，所以每次要新開節點，在合并的時候多剪枝減少棧調用和新開節點。
如果嘗試將詢問離線掛在每個 SCC 上的話，\(10^6\) 的無序 vector 應該還不如存新節點。

如果亂開東西大概率空間會炸。
一共有 \(10^6\) 個 SCC，注意到線段樹上實際有非常多節點都連向同一個節點每次新建的點并不會很多。
實際精細計算一下空間只要 \(9\times 10^7\) 個 int 就行。千萬不要亂開 vector。

留下不到一百兆給棧調用和臨時的隊列啥的應該是差不多夠了，事實上對于數據是剛剛好。

代碼

const int N = 1510,LG = 21;
int n,m,q,seed;
char s[N][N];
int dx[4] = {-1,+1,+0,+0};
int dy[4] = {+0,+0,-1,+1};
inline int id(int x,int y){
	return m*(x-1)+y;
}
struct{
	int to,nex;
}edge[N*N*3];
int head[N*N],edge_num,ind[N*N];
inline void add(int x,int y){
	edge[++edge_num].to = y;
	edge[edge_num].nex = head[x];
	head[x] = edge_num;
}
int dfn[N*N],low[N*N],st[N*N],id_scc[N*N],dtop,stop,col_cnt;
inline void tarjan(int now){
	dfn[now] = low[now] = ++dtop;
	st[++stop] = now;
	for(int i=head[now];i;i=edge[i].nex){
		int tto = edge[i].to;
		if(!dfn[tto]){
			tarjan(tto);
			low[now] = Min(low[tto],low[now]);
		}
		else if(!id_scc[tto]) low[now] = Min(low[now],dfn[tto]);
	}
	if(low[now]==dfn[now]){
		++col_cnt;
		while(st[stop]^now){
			id_scc[st[stop]] = col_cnt;
			--stop;
		}
		id_scc[st[stop]] = col_cnt;
		--stop;
	}
	head[now] = 0;
}
struct node{
	int ls,rs;
}tr[N*N*LG];
int rt[N*N],cnt;
inline int merge(int u,int v,int nl,int nr){
	if(!u || !v) return u|v;
	if(u==v) return u;
	int p = ++cnt;
    if(nl==nr){
		tr[p].ls = tr[u].ls | tr[v].ls;
        return p;
    }
    int mid = (nl+nr) >> 1;
    tr[p].ls = merge(tr[u].ls,tr[v].ls,nl,mid);
    tr[p].rs = merge(tr[u].rs,tr[v].rs,mid+1,nr);
    return p;
}
inline void insert(int &p,int nl,int nr,int x){
	if(!p) p  = ++cnt;
	int mid = (nl+nr) >> 1;
	if(nl==nr){
		tr[p].ls = 1;
		return ;
	}
	if(x<=mid) insert(tr[p].ls,nl,mid,x);
	else insert(tr[p].rs,mid+1,nr,x);
}
inline int query(int p,int nl,int nr,int x){
	if(!p) return 0;
	int mid = (nl+nr) >> 1;
	if(nl==nr) return tr[p].ls;
	if(x<=mid) return query(tr[p].ls,nl,mid,x);
	else return query(tr[p].rs,mid+1,nr,x);
}
inline void topo(){
	queue <int> q;
	for(int i=1;i<=col_cnt;++i){
		insert(rt[i],1,col_cnt,i);
		if(!ind[i]) q.push(i);
	}
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for(int i=head[now];i;i=edge[i].nex){
			int tto = edge[i].to;
			rt[tto] = merge(rt[tto],rt[now],1,col_cnt);
			--ind[tto];
			if(!ind[tto]) q.push(tto);
		}
	}
}
int main(){
	// freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);

	read(n,m,q,seed);
	init(seed);
	for(int i=1;i<=n;++i){
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;++j){
			for(int t=0;t<4;++t){
				if(s[i][j]=='U' && t==0) continue;
				if(s[i][j]=='D' && t==1) continue;
				if(s[i][j]=='L' && t==2) continue;
				if(s[i][j]=='R' && t==3) continue;
				int tx = i+dx[t];
				int ty = j+dy[t];
				if(tx<1 || tx>n || ty<1 || ty>m) continue;
				add(id(i,j),id(tx,ty));
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(!dfn[id(i,j)]) tarjan(id(i,j));
		}
	}
	edge_num = 0;
	for(int i=1;i<=n;++i){ 
		for(int j=1;j<=m;++j){
			for(int t=0;t<4;++t){
				if(s[i][j]=='U' && t==0) continue;
				if(s[i][j]=='D' && t==1) continue;
				if(s[i][j]=='L' && t==2) continue;
				if(s[i][j]=='R' && t==3) continue;
				int tx = i+dx[t];
				int ty = j+dy[t];
				if(tx<1 || tx>n || ty<1 || ty>m) continue;
				if(id_scc[id(i,j)]^id_scc[id(tx,ty)]){
					add(id_scc[id(tx,ty)],id_scc[id(i,j)]);
					++ind[id_scc[id(i,j)]];
				}
			}
		}
	}
	topo();
	for(int i=1,a,b,x,y;i<=q;++i){
		a = get(1,n); b = get(1,m); x = get(1,n); y = get(1,m);
		query(rt[id_scc[id(a,b)]],1,col_cnt,id_scc[id(x,y)]) ? putchar('1') : putchar('0');
	}

	// fclose(stdin);
	// fclose(stdout);
	return 0;
}

后話

機房里大家都覺得這種東西非常假（我也覺得很假，但是就是寫了然后過了），但實測這玩意跑得飛快。

我們在做合并的時候，只要發現處于同一個點就可以直接退出。而題里給出的圖，會使得有非常多的線段樹共用了同一個節點，合并復雜度事實上非常跑不滿。

根據我本人精心構造的數據以及對數據點的判斷，線段樹新開的節點實際非常少大概在 \(O(n^2\log{n^2})\)，合并次數大概在 \(O(n\log^2n)\) 級別。這是綽綽有余的。