刷题
CF780G Andryusha and Nervous Barriers
比较简单，先按照高度排序并重编号，扫描线找边缘下落的球分裂的第一块板子，这部分可以线段树二分，找编号最大的要求高度超过它的板子。
可以发现依赖关系一定是编号大依赖编号小，可以递推。
点击查看代码
#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int N=1e5+5,mod=1e9+7;
int h,w,n,cnt,ch[N][2],p[N],sum[N];
struct node{
int h,l,r,s;
}a[N];
vector<int> ve[N],v1[N],v2[N];
bool cmp(node x,node y)
{
return x.h<y.h;
}
struct seg_tr{
int l,r,mx;
}tr[N*4];
void build(int id,int l,int r)
{
tr[id].l=l,tr[id].r=r;
if(l==r) return;
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
void update(int id,int x,int v)
{
if(tr[id].l==tr[id].r)
{
tr[id].mx=v;
return;
}
int mid=(tr[id].l+tr[id].r)>>1;
if(x<=mid) update(lid,x,v);
else update(rid,x,v);
tr[id].mx=max(tr[lid].mx,tr[rid].mx);
}
int find(int id,int x,int v)
{
if(x==0||tr[id].mx<v) return n+1;
if(tr[id].l==tr[id].r) return tr[id].l;
int mid=(tr[id].l+tr[id].r)>>1,t=n+1;
if(x>mid) t=find(rid,x,v);
if(t==n+1) return find(lid,x,v);
return t;
}
void insert(int x)
{
if(!ch[x][0]) ch[x][0]=ch[x][1]=find(1,x-1,a[x].h);
else ch[x][1]=find(1,x-1,a[x].h);
}
int main()
{
scanf("%d%d%d",&h,&w,&n);
if(n==0)
{
printf("%d",w);
return 0;
}
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&a[i].h,&a[i].l,&a[i].r,&a[i].s);
a[i].s+=a[i].h;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
v1[a[i].l].push_back(i),v2[a[i].r].push_back(i);
if(a[i].l!=1) ve[a[i].l-1].push_back(i);
if(a[i].r!=w) ve[a[i].r+1].push_back(i);
}
build(1,1,n);
for(int i=1;i<=w;i++)
{
for(int j=0;j<v1[i].size();j++)
{
update(1,v1[i][j],a[v1[i][j]].s);
}
for(int j=0;j<ve[i].size();j++)
{
insert(ve[i][j]);
}
p[i]=find(1,n,h+1);
for(int j=0;j<v2[i].size();j++)
{
update(1,v2[i][j],0);
}
}
sum[n+1]=1;
for(int i=1;i<=n;i++)
{
sum[i]=(sum[ch[i][0]]+sum[ch[i][1]])%mod;
// printf("%d %d\n",ch[i][0],ch[i][1]);
}
int ans=0;
for(int i=1;i<=w;i++) ans=(ans+sum[p[i]])%mod;
printf("%d",ans);
return 0;
}
CF1578B Building Forest Trails
首先把圆拍到序列上，要求每条边 \(x<y\)，如果两条边 \((x_1,y_1),(x_2,y_2)\) 满足 \(x_1\le x_2\le y_1 \le y_2\) ，那么就会交叉。
考虑对每个连通块的连边方式做一个改变，变为按顺序从小到大连，而且观察到每个连通块构成的区间要么包含，要么不交。
这里应该会有一个 \(\log^2\) 的做法，就是记录一下 pre 和 next，然后线段树二分。
实际上还能更优，考虑记录每个 \(x\) 上方的线的数量 \(h_x\)，不包括连到 \(x\) 的线。
可以发现相邻两个点之间的 \(h_x\) 的变化量不超过 1，因为要么在上一个点开了一条新线，要么在这里收回一条线。
接下来考虑哪些线会和 \((x,y)\) 交叉，一种开头在 \(x\) 前面，结尾在中间，那么必然有一条线经过 \(x\)，因为区间相互包含或不交，那么在中间的收束点的 \(h\) 一定是比 \(h_x\) 小的。
所以每次可以选 \(h_x,h_y\) 中较大的去找，然后合并区间。
合并分为两种情况，一是不交，那么前面右端连后面左端，一种是包含，那么就是去掉覆盖小区间的那一段，再加上小区间到大区间的两条边，其实就是小区间上的覆盖条数 -1。
点击查看代码
#include<cstdio>
#include<algorithm>
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int N=2e5+5;
int n,m,f[N],l[N],r[N],ans[N*2],cnt;
struct seg_tr{
int l,r,mn,lazy;
}tr[N*4];
int find(int x)
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
void build(int id,int l,int r)
{
tr[id].l=l,tr[id].r=r;
if(l==r) return;
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
void pushdown(int id)
{
if(tr[id].lazy)
{
tr[lid].lazy+=tr[id].lazy,tr[lid].mn+=tr[id].lazy;
tr[rid].lazy+=tr[id].lazy,tr[rid].mn+=tr[id].lazy;
tr[id].lazy=0;
}
}
void update(int id,int l,int r,int v)
{
if(l>r) return;
if(tr[id].l==l&&tr[id].r==r)
{
tr[id].mn+=v,tr[id].lazy+=v;
return;
}
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid) update(lid,l,r,v);
else if(l>mid) update(rid,l,r,v);
else update(lid,l,mid,v),update(rid,mid+1,r,v);
tr[id].mn=min(tr[lid].mn,tr[rid].mn);
}
int query(int id,int x)
{
if(tr[id].l==tr[id].r)
{
return tr[id].mn;
}
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1;
if(x<=mid) return query(lid,x);
else return query(rid,x);
}
int findl(int id,int x,int v)
{
if(tr[id].mn>=v) return n+1;
if(tr[id].l==tr[id].r) return tr[id].l;
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1,t=n+1;
if(x<=mid) t=findl(lid,x,v);
if(t==n+1) return findl(rid,x,v);
return t;
}
int findr(int id,int x,int v)
{
if(tr[id].mn>=v) return 0;
if(tr[id].l==tr[id].r) return tr[id].l;
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1,t=0;
if(x>mid) t=findr(rid,x,v);
if(t==0) return findr(lid,x,v);
return t;
}
void merge(int x,int y)
{
if(l[x]>l[y]) swap(x,y);
if(r[x]<l[y])
{
update(1,r[x]+1,l[y]-1,1);
// printf("b1 %d %d\n",r[x]+1,l[y]-1);
}
else
{
update(1,l[y],r[y],-1);
// printf("a-1 %d %d %d %d\n",l[x],r[x],l[y],r[y]);
}
r[x]=max(r[x],r[y]),f[y]=x;
}
int main()
{
scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1;i<=n;i++)
{
f[i]=l[i]=r[i]=i;
}
while(m--)
{
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(x>y) swap(x,y);
if(opt==2)
{
if(find(x)==find(y)) ans[++cnt]=1;
else ans[++cnt]=0;
continue;
}
if(find(x)==find(y)) continue;
int v1=query(1,x),v2=query(1,y);
// printf("%d %d\n",v1,v2);
while(find(x)!=find(y))
{
if(v1>=v2)
{
int t=findl(1,x+1,v1);
if(t>=y) break;
merge(find(x),find(t));
v1=query(1,x);
}
else
{
int t=findr(1,y-1,v2);
// printf("%d\n",t);
if(t<=x) break;
merge(find(y),find(t));
v2=query(1,y);
}
}
if(find(x)!=find(y)) merge(find(x),find(y));
}
for(int i=1;i<=cnt;i++)
{
printf("%d",ans[i]);
}
return 0;
}
CF1083C Max Mex
先考虑怎么处理一组询问，就是依次加入每个点，然后判断是否在一条链上。
然后考虑上树，这里可以维护一个更强的限制，就是每个区间 \([l,r]\) 内的是否都在一条链上。
合并上就是判断两个链是否能拼在一起，一种方法就是维护端点，然后一侧往另一侧插入，最后线段树二分。
点击查看代码
#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int N=2e5+5;
int n,head[N],edgenum,cnt,t[N*2],b[N];
int dep[N],dfn[N],siz[N],idx,p[N],in[N];
struct edge{
int to,nxt;
}e[N];
void add_edge(int u,int v)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
head[u]=edgenum;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1,dfn[u]=++idx;
siz[u]=1,in[u]=cnt+1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
t[++cnt]=u;
dfs(v,u);
siz[u]+=siz[v];
}
t[++cnt]=u;
}
struct ST_table{
int l2[N*2],st[N*2][20],mn[N*2][20];
void build()
{
for(int i=1;i<=cnt;i++)
{
st[i][0]=t[i],mn[i][0]=dep[t[i]];
if(i!=1) l2[i]=l2[i/2]+1;
}
for(int i=1;i<20;i++)
{
for(int j=1;j+(1<<i)-1<=cnt;j++)
{
mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]);
if(mn[j][i-1]==mn[j][i]) st[j][i]=st[j][i-1];
else st[j][i]=st[j+(1<<(i-1))][i-1];
}
}
}
int query(int l,int r)
{
l=in[l],r=in[r];
if(l>r) swap(l,r);
int k=l2[r-l+1];
if(mn[l][k]<mn[r-(1<<k)+1][k]) return st[l][k];
return st[r-(1<<k)+1][k];
}
}ST;
struct seg_tr{
int l,r,x,y,fl;
}tr[N*4];
bool check(int x,int y)
{
if(dfn[x]<=dfn[y]&&dfn[x]+siz[x]>dfn[y]) return 1;
return 0;
}
pair<int,int> merge(int x,int y,int z)
{
if(dep[x]>dep[y]) swap(x,y);
if(check(y,z)) return {x,z};
if(check(x,y))
{
if(check(z,y)&&check(x,z)) return {x,y};
int t=ST.query(z,y);
if(check(t,x)) return {y,z};
return {0,0};
}
if(check(x,z)) return {z,y};
int t=ST.query(x,y);
if(check(t,z)&&(check(z,x)||check(z,y))) return {x,y};
return {0,0};
}
void pushup(int id)
{
tr[id].fl=tr[lid].fl&tr[rid].fl;
if(!tr[id].fl) return;
pair<int,int> p=merge(tr[lid].x,tr[lid].y,tr[rid].x);
if(p.first==0)
{
tr[id].fl=0;
return;
}
p=merge(p.first,p.second,tr[rid].y);
if(p.first==0) tr[id].fl=0;
else tr[id].x=p.first,tr[id].y=p.second;
}
void build(int id,int l,int r)
{
tr[id].l=l,tr[id].r=r;
if(l==r)
{
tr[id].fl=1,tr[id].x=tr[id].y=b[l];
return;
}
int mid=(tr[id].l+tr[id].r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
// printf("%d %d %d\n",tr[id].l,tr[id].r,tr[id].fl);
}
void update(int id,int x,int v)
{
if(tr[id].l==tr[id].r)
{
tr[id].x=tr[id].y=v;
return ;
}
int mid=(tr[id].l+tr[id].r)>>1;
if(x<=mid) update(lid,x,v);
else update(rid,x,v);
pushup(id);
}
int find(int id,int x,int y)
{
// printf("%d %d\n",x,y);
if(tr[id].l==tr[id].r) return tr[id].l;
if(!tr[lid].fl) return find(lid,x,y);
pair<int,int> p=merge(x,y,tr[lid].x);
if(!p.first) return find(lid,x,y);
p=merge(p.first,p.second,tr[lid].y);
if(!p.first) return find(lid,x,y);
return find(rid,p.first,p.second);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
p[i]++;
b[p[i]]=i;
}
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
add_edge(x,i);
}
dfs(1,0);
ST.build();
build(1,1,n);
// for(int i=1;i<=n;i++) printf("%d ",siz[i]);
int q;
scanf("%d",&q);
while(q--)
{
int opt,x,y;
scanf("%d",&opt);
if(opt==2)
{
if(tr[1].fl)
{
printf("%d\n",n);
continue;
}
printf("%d\n",find(1,b[1],b[1])-1);
}
else
{
scanf("%d%d",&x,&y);
swap(p[x],p[y]),swap(b[p[x]],b[p[y]]);
update(1,p[x],x),update(1,p[y],y);
}
}
return 0;
}
P11833 [省选联考 2025] 推箱子
弱智但比较难写。
按时间排序，每次优先满足时间限制较紧的。考虑满足的过程中，以向左移动为例。
在移动的过程中考虑会碰到哪些箱子，记当前下标为 \(i\)，那么现在移动的结果就是 \(b_i-k,b_i-k+1,\dots,b_i\)，所以在它前面的点 \(j\)，如果位置在 \(b_i-i+j\) 的后面，就要移动。
然后考虑如何快速找，这里给一个较为方便的解法，首先把箱子向右移动 \(i-j\)，这样每个点的目标位置就是 \(b_i\)，就可以线段树二分。
最后就是区间加等差数列和区间赋值等差数列，外加区间求和计算贡献，向右移动同理。
点击查看代码
#include<cstdio>
#include<algorithm>
#define ll long long
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int N=2e5+5;
int c,T,n,a[N],b[N];
ll t[N];
struct seg_tr{
int l,r,cov,add,addt,mn,mx;
ll sum;
}tr[N*4];
inline void clear(int id)
{
tr[id].cov=-1,tr[id].add=tr[id].addt=0;
}
inline void pushup(int id)
{
tr[id].sum=tr[lid].sum+tr[rid].sum;
tr[id].mn=tr[lid].mn,tr[id].mx=tr[rid].mx;
}
inline void build(int id,int l,int r)
{
tr[id].l=l,tr[id].r=r,clear(id);
if(l==r)
{
tr[id].sum=tr[id].mn=tr[id].mx=a[l];
return;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
inline void add(int id,int x,int y)
{
int l=tr[id].l,r=tr[id].r;
tr[id].mn+=x,tr[id].mx+=x+y*(r-l);
tr[id].sum+=1ll*(2*x+y*(r-l))*(r-l+1)/2;
// printf("%d %d %d %d %lld\n",l,r,tr[id].mn,tr[id].mx,tr[id].sum);
tr[id].add+=x,tr[id].addt+=y;
}
inline void cover(int id,int v)
{
tr[id].add=tr[id].addt=0;
tr[id].mn=tr[id].mx=tr[id].cov=v;
tr[id].sum=1ll*v*(tr[id].r-tr[id].l+1);
}
inline void pushdown(int id)
{
if(tr[id].cov!=-1)
{
cover(lid,tr[id].cov),cover(rid,tr[id].cov);
tr[id].cov=-1;
}
if(!tr[id].add&&!tr[id].addt) return;
add(lid,tr[id].add,tr[id].addt);
add(rid,tr[id].add+(tr[rid].l-tr[lid].l)*tr[id].addt,tr[id].addt);
tr[id].add=tr[id].addt=0;
}
inline void update(int id,int l,int r,int x,int v)
{
if(tr[id].l==l&&tr[id].r==r)
{
// printf("b");
// if(r==6) printf("%d %d %d %d\n",l,r,x,v);
add(id,x,v);
return;
}
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid) update(lid,l,r,x,v);
else if(l>mid) update(rid,l,r,x,v);
else update(lid,l,mid,x,v),update(rid,mid+1,r,x+v*(mid+1-l),v);
pushup(id);
}
inline void change(int id,int l,int r,int x,int v)
{
if(tr[id].l==l&&tr[id].r==r)
{
cover(id,x);
add(id,0,v);
return;
}
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid) change(lid,l,r,x,v);
else if(l>mid) change(rid,l,r,x,v);
else change(lid,l,mid,x,v),change(rid,mid+1,r,x+v*(mid+1-l),v);
pushup(id);
}
inline ll query(int id,int l,int r)
{
if(tr[id].l==l&&tr[id].r==r)
{
// printf("%d %d %d\n",l,r,tr[id].sum);
return tr[id].sum;
}
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid) return query(lid,l,r);
else if(l>mid) return query(rid,l,r);
else return query(lid,l,mid)+query(rid,mid+1,r);
}
inline int findl(int id,int x)
{
if(tr[id].l==tr[id].r) return tr[id].l;
pushdown(id);
if(tr[lid].mx<=x) return findl(rid,x);
return findl(lid,x);
}
inline int findr(int id,int x)
{
if(tr[id].l==tr[id].r) return tr[id].l;
pushdown(id);
if(tr[rid].mn>=x) return findr(lid,x);
return findr(rid,x);
}
struct node{
ll t;
int id;
}p[N];
inline bool cmp(node x,node y)
{
return x.t<y.t;
}
inline ll move_left(int id,int st,int ed)
{
update(1,1,id,id-1,-1);
int x=findl(1,ed);
// if(id==79) printf("a%d ",x);
ll val=query(1,x,id)-1ll*(id-x+1)*ed;
update(1,1,id,-id+1,1);
change(1,x,id,ed-id+x,1);
return val;
}
inline ll move_right(int id,int st,int ed)
{
update(1,id,n,0,-1);
int x=findr(1,ed);
ll val=1ll*(x-id+1)*ed-query(1,id,x);
update(1,id,n,0,1);
change(1,id,x,ed,1);
return val;
}
inline bool solve()
{
ll tmp=0;
for(int i=1;i<=n;i++)
{
int x=p[i].id;
int now=query(1,x,x);
if(now==b[x]) continue;
if(now<b[x]) tmp+=move_right(x,now,b[x]);
else tmp+=move_left(x,now,b[x]);
// printf("%d %d %d %d %d\n",i,tmp,x,now,b[x]);
if(tmp>t[x]) return 0;
}
return 1;
}
int main()
{
// freopen("1.txt","r",stdin);
scanf("%d%d",&c,&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%lld",&a[i],&b[i],&t[i]);
p[i]=(node){t[i],i};
}
// ll sum=0;
// for(int i=41;i<=139;i++) sum+=a[i];
// printf("%lld\n",sum-(139-41)*(139-40)/2);
// if(T>1||T==0) continue;
sort(p+1,p+n+1,cmp);
build(1,1,n);
// for(int i=1;i<=n;i++) printf("%d ",query(1,i,i));
if(solve()) printf("Yes\n");
else printf("No\n");
}
return 0;
}
P11831 [省选联考 2025] 追忆
因为是自己做的，所以比较神秘。
首先 bitset 搞出连通性，然后考虑对操作分块，但是还有 \(l,r\) 的限制，所以继续对值域分块。
这个时候可以对每个值域块跑 \(O(n)\) 的递推找最大值，散块暴力判断。被操作的部分因为值不确定，所以单独拿出来求出值后求贡献。
这里注意一下常数，对每个操作块所有整块一起跑，然后在询问处取需要的，这样常数比较小。
块长因为 \(n,q\) 同阶，所以可以取到 \(n^{\frac{2}{3}}\)，时间复杂度 \(O(\frac{n^2}{w}+n^{\frac{5}{3}})\)
点击查看代码
#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=1e5+5;
const int Inf = 2e9;
bool Beg;
struct IO {
static const int Size = (1 << 21);
char buf[Size], *p1, *p2; int st[105], Top;
~IO() {clear();}
il void clear() {fwrite(buf, 1, Top, stdout); Top = 0;}
il char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Size, stdin), p1 == p2) ? EOF : *p1++;}
il void pc(const char c) {Top == Size && (clear(), 0); buf[Top++] = c;}
il IO &operator >> (char &c) {while(c = gc(), c == ' ' || c == '\n' || c == '\r'); return *this;}
template <typename T> il IO &operator >> (T &x) {
x = 0; bool f = 0; char ch = gc();
while(!isdigit(ch)) {if(ch == '-') f = 1; ch = gc();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
f ? x = -x : 0; return *this;
}
il IO &operator >> (string &s) {
s = ""; char c = gc();
while(c == ' ' || c == '\n' || c == '\r') c = gc();
while(c != ' ' && c != '\n' && c != '\r' && c != EOF) s += c, c = gc();
return *this;
}
il IO &operator << (const char c) {pc(c); return *this;}
template <typename T> il IO &operator << (T x) {
if(x < 0) pc('-'), x = -x;
do st[++st[0]] = x % 10, x /= 10; while(x);
while(st[0]) pc('0' + st[st[0]--]);
return *this;
}
il IO &operator << (const char *s) {for(int i = 0; s[i]; i++) pc(s[i]); return *this;}
}fin, fout;
int ct,T,n,m,q,head[N],edgenum,cnt1,cnt2,b1,b2,id[N];
int d[N],a[N],b[N],p[N],st[N],ed[N],pos[N],cnt;
int d1[N],mx[36][N],ans[N],maxn;
bool vis[N];
struct edge{
int nxt,to;
}e[N*2];
struct node{
int opt,x,y;
}c[N];
struct ques{
int t,x,l,r;
}qs[N];
bitset<N> bs[N],I;
inline void add_edge(int u,int v)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
head[u]=edgenum;
}
inline void init()
{
for(int i=1;i<=n;i++) bs[i]=I;
memset(ans,0,sizeof(ans));
memset(head,0,sizeof(head));
memset(d,0,sizeof(d));
edgenum=cnt1=cnt2=0;
}
inline void change(int l,int r)
{
for(int i=l;i<=r;i++)
{
int x=c[i].x,y=c[i].y;
if(c[i].opt==2) swap(b[x],b[y]);
else swap(a[x],a[y]),p[a[x]]=x,p[a[y]]=y;
}
}
int t1,t2;
inline void get()
{
memset(mx,0,sizeof(mx));
for(int i=1;i<=n;i++)
{
if(!vis[p[i]]) mx[pos[i]][p[i]]=b[p[i]];
}
for(int u=n;u>0;u--)
{
for(int i=head[u];i;i=e[i].nxt)
{
for(int j=1;j<=t1;j++) mx[j][u]=max(mx[j][u],mx[j][e[i].to]);
}
}
}
inline void solve(int x)
{
// if(ans[x]==n) return;
int l=qs[x].l,r=qs[x].r;
for(int i=1;i<=cnt;i++)
{
int t=id[i];
if(a[t]>=l&&a[t]<=r&&bs[qs[x].x][t]) ans[x]=max(ans[x],b[t]);
}
for(int i=l;i<=min(r,ed[pos[l]]);i++)
{
if(bs[qs[x].x][p[i]]) ans[x]=max(ans[x],b[p[i]]);
}
if(pos[l]==pos[r]) return;
for(int i=pos[l]+1;i<pos[r];i++) ans[x]=max(ans[x],mx[i][qs[x].x]);
for(int i=st[pos[r]];i<=r;i++)
{
if(bs[qs[x].x][p[i]]) ans[x]=max(ans[x],b[p[i]]);
}
}
int main()
{
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
fin>>ct>>T;
// T=1;
// printf("%d %d\n",ct,T);
while(T--)
{
fin>>n>>m>>q;
init();
for(int i=1;i<=m;i++)
{
int u,v;
fin>>u>>v;
add_edge(u,v);
d[u]++;
}
for(int i=1;i<=n;i++) bs[i][i]=1;
for(int u=n;u>0;u--)
{
for(int i=head[u];i;i=e[i].nxt)
{
bs[u]|=bs[e[i].to];
}
}
for(int i=1;i<=n;i++)
{
fin>>a[i];
p[a[i]]=i;
}
for(int i=1;i<=n;i++)
{
fin>>b[i];
}
for(int i=1;i<=q;i++)
{
int opt,x,y,z;
fin>>opt>>x>>y;
if(opt==1||opt==2) c[++cnt1]=(node){opt,x,y};
else
{
fin>>z;
qs[++cnt2]=(ques){cnt1,x,y,z};
}
}
b1=3100,b2=pow(cnt1,2.0/3.0)*1.7;
t1=(n+b1-1)/b1;
// printf("%d ",t1);
for(int i=1;i<=t1;i++)
{
st[i]=(i-1)*b1+1,ed[i]=i*b1;
}
ed[t1]=n;
for(int i=1;i<=t1;i++)
{
for(int j=st[i];j<=ed[i];j++) pos[j]=i;
}
if(b2==0)
{
get();
for(int j=1;j<=cnt2;j++)
{
solve(j);
fout<<ans[j]<<'\n';
}
continue;
}
t2=(cnt1+b2-1)/b2;
// printf("%d ",t1);
// printf("%d %d\n",n,cnt1);
// printf("%d %d %d %d %d %d\n",n,cnt1,b1,b2,t1,t2);
int tmp=1;
for(int i=1;i<=t2;i++)
{
// printf("%d ",i);
int st1=(i-1)*b2+1,ed1=min(cnt1,i*b2);
cnt=0;
int k=tmp;
while(k<=cnt2&&qs[k].t<=ed1) k++;
if(k==tmp) continue;
for(int j=st1;j<=ed1;j++)
{
if(!vis[c[j].x]) vis[c[j].x]=1,id[++cnt]=c[j].x;
if(!vis[c[j].y]) vis[c[j].y]=1,id[++cnt]=c[j].y;
}
get();
// printf("%d %d\n",k,tmp);
for(int j=tmp;j<k;j++)
{
change(max(st1,qs[j-1].t+1),qs[j].t);
solve(j);
}
change(qs[k-1].t+1,ed1);
for(int j=st1;j<=ed1;j++) vis[c[j].x]=vis[c[j].y]=0;
tmp=k;
}
for(int i=1;i<=cnt2;i++)
{
fout<<ans[i]<<'\n';
}
}
return 0;
}
浙公网安备 33010602011771号