追忆失败求卡常

#include<bits/stdc++.h>
#include<immintrin.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

#define SIZ 1568

struct bitst {
    static constexpr int SZ = SIZ;
    alignas(32) uint64_t a[SZ];

    void reset() {
        memset(a, 0, sizeof(a));
    }
    void set(int x) {
        a[x >> 6] |= 1ull << (x & 63);
    }
    void flip(int x) {
        a[x >> 6] ^= 1ull << (x & 63);
    }
    int val(int x) {
        return (a[x >> 6] >> (x & 63)) & 1;
    }

    void operator|=(const bitst &b) {
        for (int i=0;i<SZ;i+=4) {
            __m256i x = _mm256_load_si256((__m256i*)(a+i));
            __m256i y = _mm256_load_si256((__m256i*)(b.a+i));
            __m256i z = _mm256_or_si256(x,y);
            _mm256_store_si256((__m256i*)(a+i),z);
        }
    }

    void operator^=(const bitst &b) {
        for (int i=0;i<SZ;i+=4) {
            __m256i x = _mm256_load_si256((__m256i*)(a+i));
            __m256i y = _mm256_load_si256((__m256i*)(b.a+i));
            __m256i z = _mm256_xor_si256(x,y);
            _mm256_store_si256((__m256i*)(a+i),z);
        }
    }

    void operator&=(const bitst &b) {
        for (int i=0;i<SZ;i+=4) {
            __m256i x = _mm256_load_si256((__m256i*)(a+i));
            __m256i y = _mm256_load_si256((__m256i*)(b.a+i));
            __m256i z = _mm256_and_si256(x,y);
            _mm256_store_si256((__m256i*)(a+i),z);
        }
    }
};

#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

template <typename Tp> static inline void read(Tp&x){
    int f=1;x=0;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-'?-f:f),c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=f;
}
template <typename Tp,typename...Ts> static inline void read(Tp&x,Ts&...Args){read(x),read(Args...);}

template <typename Tp> static inline void print(Tp x){
    if(x<0) putchar('-'),x=-x;
    if(x<=9) putchar(x^48);
    else print(x/10),putchar((x%10)^48);
}
template <typename Tp,typename...Ts> static inline void print(Tp x,Ts ...Args){print(x),putchar('\n'),print(Args...);}

struct edge{int to,nxt;}e[200010];int head[100010],ecnt=1;
static inline void addedge(int x,int y){e[ecnt]={y,head[x]},head[x]=ecnt++;}

int n,m,s;

// bitset<100010> bts[100010];
bitst bts[100010];

int a[100010],b[100010];
int rnka[100010];

const int B1=4096,B2=5250;

int OPT[200010],X[200010],Y[200010],Z[200010];

// struct operations{
//     int opt;
//     int x,y,z;
// }q[200010];

bool edited[100010];
int tmp[100010],tmp_siz;

int dp[100010];
int Ans[200010];

int main(){
    // freopen("..\\samples\\P11831_23.in","r",stdin);
    // freopen("..\\samples\\xxx.out","w",stdout);
    // freopen("xxx.in","r",stdin);
    // freopen("xxx.out","w",stdout);
    // cin.tie(0)->sync_with_stdio(false);
    
    int c,T;read(c,T);
    while(T--){
        read(n,m,s);
        for(int i=1;i<=m;i++){
            int x,y;read(x,y);
            addedge(y,x);
        }

        // for(int i=1;i<=n;i++) bts[i][i]=true;
        for(int i=1;i<=n;i++) bts[i].set(i);
        for(int x=n;x>=1;x--) for(int i=head[x],y=e[i].to;i;i=e[i].nxt,y=e[i].to) bts[y]|=bts[x];

        for(int i=1;i<=n;i++) read(a[i]),rnka[a[i]]=i;
        for(int i=1;i<=n;i++) read(b[i]);

        for(int i=1;i<=s;i++){
            read(OPT[i],X[i],Y[i]);
            if(OPT[i]==3) read(Z[i]);
        }

        for(int ql=1,qr=min(ql+B2-1,s);ql<=s;ql+=B2,qr=min(ql+B2-1,s)){
            for(int i=ql;i<=qr;i++) if(OPT[i]!=3) edited[X[i]]=edited[Y[i]]=true;
            for(int i=1;i<=n;i++) if(edited[i]) tmp[++tmp_siz]=i;
            for(int al=1,ar=min(al+B1-1,n);al<=n;al+=B1,ar=min(al+B1-1,n)){
                for(int i=al;i<=ar;i++) if(!edited[rnka[i]]) dp[rnka[i]]=b[rnka[i]];
                for(int x=n;x>=1;x--) for(int i=head[x],y=e[i].to;i;i=e[i].nxt,y=e[i].to) dp[y]=max(dp[y],dp[x]);
                for(int i=ql;i<=qr;i++) if(OPT[i]==3&&Y[i]<=al&&ar<=Z[i]) Ans[i]=max(Ans[i],dp[X[i]]);

                for(int i=1;i<=n;i++) dp[i]=0;
            }
            for(int i=ql;i<=qr;i++){
                if(OPT[i]!=3) continue;
                int l_end=(Y[i]-1)/B1*B1+B1,r_begin=(Z[i]-1)/B1*B1+1;
                if(l_end>r_begin){
                    // for(int p=Y[i];p<=Z[i];p++) if(bts[X[i]][rnka[p]]&&!edited[rnka[p]]) Ans[i]=max(Ans[i],b[rnka[p]]);
                    for(int p=Y[i];p<=Z[i];p++) if(bts[X[i]].val(rnka[p])&&!edited[rnka[p]]) Ans[i]=max(Ans[i],b[rnka[p]]);
                }else{
                    // for(int p=Y[i];p<=l_end;p++) if(bts[X[i]][rnka[p]]&&!edited[rnka[p]]) Ans[i]=max(Ans[i],b[rnka[p]]);
                    for(int p=Y[i];p<=l_end;p++) if(bts[X[i]].val(rnka[p])&&!edited[rnka[p]]) Ans[i]=max(Ans[i],b[rnka[p]]);
                    // for(int p=r_begin;p<=Z[i];p++) if(bts[X[i]][rnka[p]]&&!edited[rnka[p]]) Ans[i]=max(Ans[i],b[rnka[p]]);
                    for(int p=r_begin;p<=Z[i];p++) if(bts[X[i]].val(rnka[p])&&!edited[rnka[p]]) Ans[i]=max(Ans[i],b[rnka[p]]);
                }
            }
            for(int i=ql;i<=qr;i++){
                if(OPT[i]==1) swap(a[X[i]],a[Y[i]]),swap(rnka[a[X[i]]],rnka[a[Y[i]]]);
                else if(OPT[i]==2) swap(b[X[i]],b[Y[i]]);
                // else if(OPT[i]==3) for(int p=1,x=tmp[p];p<=tmp_siz;p++,x=tmp[p]) if(bts[X[i]][x]&&Y[i]<=a[x]&&a[x]<=Z[i]) Ans[i]=max(Ans[i],b[x]);
                else if(OPT[i]==3) for(int p=1,x=tmp[p];p<=tmp_siz;p++,x=tmp[p]) if(bts[X[i]].val(x)&&Y[i]<=a[x]&&a[x]<=Z[i]) Ans[i]=max(Ans[i],b[x]);
            }

            for(int i=1;i<=n;i++) edited[i]=false;
            tmp_siz=0;
        }
        for(int i=1;i<=s;i++) if(OPT[i]==3) print(Ans[i]),putchar(0xa);

        ecnt=1;
        for(int i=1;i<=n;i++) head[i]=0,bts[i].reset();
        for(int i=1;i<=m;i++) Ans[i]=0;
    }
    
    # ifdef TakanashiHoshino
    cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
    # endif
    return 0;
}