「ROI 2019 Day1」运输 20/19

题目大意：

给定一个带权$DAG$，$1$为起始点，给定小常数$p$

每次查询一个点$u$，一个权值$r$，问是否存在一条路径$1\ldots u$，其长度$x$满足$r\leq x\leq \frac{p} {p-1}\cdot r$

转换一下，$dp$每个点是否存在$r$，那么对于路径的权值$x$，合法的$r$即为$[\frac{p-1} {p}\cdot x,x]$

对于任意两个区间，如果其相交，则可以合并，并且用两个区间中最小和最大的$x$来表示这个区间

而不相交的区间最多只有$\log_{\frac{p} {p-1} } w$段，大概$700$段

任意时刻，每个点的$dp$情况可以用$700$段不交的区间表示，转移可以归并数组进行

因此维护$dp$复杂度为$O(m\log_{\frac{p} {p-1} } w)$常数极小，单次查询复杂度为$O(\log \log_{\frac{p} {p-1} } w)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=5e5+10;

int n,m,q,p;
struct Interval{
	ll l,r,x,y;
	Interval(ll a,ll b){ 
		x=a,y=b;
		l=(x*(p-1)+p-1)/p,r=y;
	}
	void Add(ll c){
		x+=c,y+=c;
		l=(x*(p-1)+p-1)/p,r=y;
	}
	bool operator & (const Interval &__) const { return min(r,__.r)>=max(l,__.l)-1; }
	Interval operator + (const Interval &__) const { return Interval(min(x,__.x),max(y,__.y)); }
	bool operator < (const ll &x) const {
		return r<x;
	}
};
vector <Interval> dp[N];

struct Edge{
	int to,nxt; ll w;
} e[N];
int head[N],ecnt;
void AddEdge(int u,int v,ll w){
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}
void Trans(vector <Interval> &x,vector <Interval> y,ll c){
	for(auto &i:y) i.Add(c);
	vector <Interval> res;
	int p1=0,p2=0,s1=x.size(),s2=y.size();
	while(p1<s1 || p2<s2) {
		if(p1<s1 && (p2==s2 || x[p1].l<=y[p2].l)) {
			if(res.size() && *res.rbegin()&x[p1]) res[res.size()-1]=*res.rbegin()+x[p1++];
			else res.pb(x[p1++]);
		} else {
			if(res.size() && *res.rbegin()&y[p2]) res[res.size()-1]=*res.rbegin()+y[p2++];
			else res.pb(y[p2++]);
		}
	}
	x=res;
}

int main(){
	rep(kase,1,rd()) {
		n=rd(),m=rd(),q=rd(),p=rd();
		rep(i,1,n) head[i]=ecnt=0;
		rep(i,1,m){
			int u=rd(),v=rd(); ll w=rd<ll>();
			AddEdge(u,v,w);
		}
		rep(i,1,n) dp[i].clear();
		dp[1].pb(Interval(0,0));
		rep(u,1,n) {
			for(int i=head[u];i;i=e[i].nxt) {
				Trans(dp[e[i].to],dp[u],e[i].w);
			}
		}
		while(q--){
			int x=rd(); ll y=rd<ll>();
			auto p=lower_bound(dp[x].begin(),dp[x].end(),y);
			if(p!=dp[x].end() && p->l<=y) putchar('1');
			else putchar('0');
		}
		puts("");
	}
}