题解：P11340 「COI 2019」TENIS

· · 题解

Solution

今年做的最后一道题了 /kel

如果 i 某一维度比 j 强，则 i \to j 建立有向边。

这个东西的边数是严格包含一个竞赛图的，所以 \rm SCC 缩点后会变成这样的形态：

因此最上面那个 \rm SCC 满足：设集合为 S，则 \forall 1 \le i \le 3，u \in S，v \notin S，p_{i,u} > p_{i,v}，其中 p 表示的是一个人在这个场地上的能力。

这又等价于：三个能力从大到小排列的最小前缀，使得三个前缀元素构成的集合相同。设前缀长度为 len。

等价于：设 r_{i,j} 为 j 在 i 场上的排名，则 \max\{r_{1,i},r_{2,i},r_{3,i}\} \le len 的 i 有 len 个。

显然可以使用线段树维护这个东西，复杂度 O(q \log n)。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,q,rnk[MAXN][4],tag[MAXN<<2],mn[MAXN<<2];
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
void push_down(int k,int l,int r) {return tag[lson]+=tag[k],tag[rson]+=tag[k],mn[lson]+=tag[k],mn[rson]+=tag[k],tag[k]=0,void();}
void update(int k,int l,int r,int x,int y,int v) {
    if(x<=l&&r<=y) return tag[k]+=v,mn[k]+=v,void();
    push_down(k,l,r);
    if(x<=mid) update(lson,l,mid,x,y,v);
    if(y>mid) update(rson,mid+1,r,x,y,v);
    return mn[k]=min(mn[lson],mn[rson]),void(); 
}
int bfind(int k,int l,int r) {
    if(mn[k]>0) return -1;
    if(l==r) return l;
    push_down(k,l,r);
    int ans=bfind(lson,l,mid);
    if(ans!=-1) return ans;
    return bfind(rson,mid+1,r);
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    ffor(i,1,n) {int v;cin>>v,rnk[v][1]=i;}
    ffor(i,1,n) {int v;cin>>v,rnk[v][2]=i;}
    ffor(i,1,n) {int v;cin>>v,rnk[v][3]=i;}
    ffor(i,1,n) update(1,1,n,i,n,1);
    ffor(i,1,n) update(1,1,n,max({rnk[i][1],rnk[i][2],rnk[i][3]}),n,-1);
    ffor(i,1,q) {
        int op;
        cin>>op;
        if(op==1) {
            int x;
            cin>>x;
            if(bfind(1,1,n)>=rnk[x][1]) cout<<"DA\n";
            else cout<<"NE\n";
        }
        else {
            int p,a,b;
            cin>>p>>a>>b;
            update(1,1,n,max({rnk[a][1],rnk[a][2],rnk[a][3]}),n,1);
            update(1,1,n,max({rnk[b][1],rnk[b][2],rnk[b][3]}),n,1);
            swap(rnk[a][p],rnk[b][p]);
            update(1,1,n,max({rnk[a][1],rnk[a][2],rnk[a][3]}),n,-1);
            update(1,1,n,max({rnk[b][1],rnk[b][2],rnk[b][3]}),n,-1);
        }
    }
    return 0;
}