【線段樹分治MOBAN】 LUOGU5787

一道線段樹分治模闆題。

​​https://www.luogu.com.cn/problem/P5787​​

線段樹分治用于解決在時間上插入的離線處理方法。具體将時間軸建立為一棵線段樹，一個操作對時間軸的影響插入logn段線段樹中，最後周遊線段樹到時間路徑上進行操作。相對于CDQ分治，此時詢問被看做是一個時間點。

就挺棒的，該題就參照NOIP2010關押罪犯那麼搞來判斷二分圖，每個點拆分為x和x+n(x與它的敵人)，當x與y連邊，則相當于x與y+N連邊，y與x+n連邊(敵人的敵人就是朋友),當然，如果x與x+n連邊了則證明不是二分圖。

#include<bits/stdc++.h>

using namespace std;
const int maxn = 2e5+5;
int n;
int a[maxn];
char ss[maxn];
int b[maxn],r[maxn];
int bl,rl;
void sol() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    bl = rl = 0;
    scanf("%s",&ss[1]);
    for(int i=1;i<=n;i++) {
        if(ss[i]=='B') b[++bl] = a[i];
        else r[++rl] = a[i];
    }
    sort(b+1,b+1+bl);
    sort(r+1,r+1+rl,greater<int>());
    bool flag = 1;
    for(int i=1;i<=bl;i++) {
        if(b[i]<i) flag = 0;
    }
    for(int i=1;i<=rl;i++) {
        if(r[i]>(n-i+1)) flag = 0;
    }
    if(flag) puts("YES");
    else puts("NO");
}

int main(){
    int t;
    cin>>t;
    while(t--) sol();
    return 0;
}