题解：P11340 [COI 2019] TENIS

__vector__ · 2025-10-04 11:44:43 · 题解

• 结论一：

  能成为冠军的人，在任意一张地图的排行榜上构成一个前缀。

• 证明：

  假设某一张地图上存在 i \lt j，且排名为 i 的人无法成为冠军，但排名为 j 的人可以成为冠军，那么由排名为 j 的人击败除了排名为 i 的人以外的所有的人，然后再由排名为 i 的人击败排名为 j 的人，那么排名为 i 的人就可以成为冠军，与假设矛盾。

• 结论二：

  三张地图的冠军前缀长度相等。

• 证明：

  假设三张地图的冠军构成的前缀长度从小到大依次为 len_1,len_2,len_3，且 len_1 \neq len_3。

  那么，对于长度为 len_3 的冠军前缀，其在另外两个排行榜上同样占据 len_3 个人，所有排名小于等于这些人的，同样构成冠军，那么也就是说 len_1 肯定大于等于 len_3，与假设矛盾。

考虑如何确定前缀的长度，假定其为 len。

那么任意一个冠军的最差排名不会高于 len。

另外，必然存在至少一个冠军的最差排名为 len，否则排名为 len 的人无论如何也无法击败任意一个冠军，也就没有排名为 len 的人能成为冠军。

那么现在已经确定了条件：

• 令选手 i 的最优排名为 l_i，最差排名为 r_i，那么 len 就是最小的位置，使得不存在任意一个区间左端点小于 len，右端点大于等于 len。

对于每个位置，记录左端点小于等于其的区间个数减去右端点小于等于其的区间个数。

这个数字肯定是一个非负整数，现在要找的就是第一个 0 的位置。

那么，考虑使用线段树，其支持以下操作：

• 区间加法。

  修改操作需要用到。

• 维护区间最小值。

  用于确定区间是否存在 0。

• 二分查找第一个 0 的位置。

  这个需要依赖区间最小值。

一种可以通过的代码实现：

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
void io(){
    freopen("champion.in","r",stdin);
    freopen("champion.out","w",stdout);
}
const int maxn=1e5+5;
struct SGT{
    int mn[maxn<<2],lazy[maxn<<2];
    int lef[maxn<<2],rig[maxn<<2];
    void pushup(int pos){
        mn[pos]=min(mn[pos<<1],mn[pos<<1|1]);
    }
    void upd(int pos,int _add){
        mn[pos]+=_add;
        lazy[pos]+=_add;
    }
    void pushdown(int pos){
        if(!lazy[pos])return;
        upd(pos<<1,lazy[pos]);
        upd(pos<<1|1,lazy[pos]);
        lazy[pos]=0;
    }
    void bd(int pos,int l,int r){
        lef[pos]=l,rig[pos]=r;
        if(l==r)return;
        int mid=(l+r>>1);
        bd(pos<<1,l,mid);
        bd(pos<<1|1,mid+1,r);
        pushup(pos);
    }
    void add(int pos,int l,int r,int _add){
        if(lef[pos]>=l&&rig[pos]<=r){
            upd(pos,_add);
            return;
        }
        pushdown(pos);
        int mid=(lef[pos]+rig[pos]>>1);
        if(mid>=l)add(pos<<1,l,r,_add);
        if(mid<r)add(pos<<1|1,l,r,_add);
        pushup(pos);
    }
    int find(int pos){
        if(lef[pos]==rig[pos]){
            return lef[pos];
        }
        pushdown(pos);
        if(mn[pos<<1]==0)return find(pos<<1);
        return find(pos<<1|1);
    }
}sgt;
int n,q;
int rklist[4][maxn];
int pos[4][maxn];
int l[maxn],r[maxn];
void solve(int id_of_test){
    read(n);
    read(q);
    memset(l,0x3f,sizeof l);
    sgt.bd(1,1,n);
    FOR(i,1,3){
        FOR(j,1,n){
            read(rklist[i][j]);
            pos[i][rklist[i][j]]=j;
            ckmn(l[rklist[i][j]],j);
            ckmx(r[rklist[i][j]],j);
        }
    }
    FOR(i,1,n){
        sgt.add(1,l[i],n,1);
        sgt.add(1,r[i],n,-1);
    }
    while(q--){
        int op;
        read(op);
        if(op==1){
            int x;
            read(x);
          //  printf("sgt.find1 = %d\n",sgt.find(1));
            if(min({pos[1][x],pos[2][x],pos[3][x]})<=sgt.find(1)){
                puts("DA");
                continue;
            }
            puts("NE");
        }else{
            int p,a,b;
            read(p);
            read(a);
            read(b);
            sgt.add(1,l[a],n,-1);
            sgt.add(1,r[a],n,1);
            sgt.add(1,l[b],n,-1);
            sgt.add(1,r[b],n,1);
            int &id1=pos[p][a],&id2=pos[p][b];
            swap(rklist[p][id1],rklist[p][id2]);
            swap(id1,id2);
            l[a]=min({pos[1][a],pos[2][a],pos[3][a]});
            r[a]=max({pos[1][a],pos[2][a],pos[3][a]});
            l[b]=min({pos[1][b],pos[2][b],pos[3][b]});
            r[b]=max({pos[1][b],pos[2][b],pos[3][b]});
            sgt.add(1,l[a],n,1);
            sgt.add(1,r[a],n,-1);
            sgt.add(1,l[b],n,1);
            sgt.add(1,r[b],n,-1);
        }
    }
}
int main()
{
    // io();
    int T;
    T=1;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}
/*
1. 对题意的理解能否和样例对的上？  
2. 每一步操作，能否和自己的想法对应上？  
3. 每一步操作的正确性是否有保证？  
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？  
*/