贪心、哈希、莫队

理解题意后可以发现警长不可能赢，因为罗宾汉每次会选最大的数删除，警长只能选次大的数删除。所以当且仅当区间中所有值都出现偶数次时警长与罗宾汉打平，否则他会输掉比赛。

我赛时错误的做法是给每个值随机一个矩阵，在矩阵序列中交替放置每个值对应的矩阵和逆矩阵，如果区间矩阵乘积为单位矩阵则认为区间符合条件。错误之处实际上还是矩阵乘法不符合交换律，虽然有 $A A^{-1} = A^{-1}A = I$ 但没有 $ABA^{-1}B^{-1} = I$，举个例子。

$$A = \left[\begin{array}{c} 1 & 2 \\ 3 & 4 \end{array}\right] , B = \left[\begin{array}{c} 5 & 6 \\ 7 & 8 \end{array}\right]$$

$$A^{-1} = \left[\begin{array}{c} -2 & 1 \\ 1.5 & -0.5 \end{array}\right] , B^{-1} = \left[\begin{array}{c} -4 & 3 \\ 3.5 & -2.5 \end{array}\right]$$

$$ABA^{-1}B^{-1} = \left[\begin{array}{c} 48 & -35 \\ 107 & -78 \end{array}\right] \neq \left[\begin{array}{c} 1 & 0 \\ 0 & 1 \end{array}\right]$$

做带方向的括号匹配倒是可以用随机矩阵，但是这个只要求出现偶数次，所以我寄了。寄寄寄，急急急，难得能做的压轴题就这样没过。

Solution 1：我一开始是想可持久化权值线段树维护区间的，但是没有手段能在把树裂出来的同时判断树叶权值是否都是偶数。

这时候就该往功能更强的根号算法想了，显然有莫队做法，可惜我没想。

直接莫队，由于 $n,q$ 同阶，时间复杂度 $O(n \sqrt{n})$。

#include<bits/stdc++.h>
using namespace std;
struct Query{int l,r,i;}q[200'005];
bitset<1'000'005> on;
bitset<200'005> ans;
int n,m,a[200'005];
void solution(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++) q[i].i=i,scanf("%d%d",&q[i].l,&q[i].r);
    const int B=sqrt(n);
    sort(q+1,q+m+1,[&](auto x,auto y){
        if(x.l/B!=y.l/B) return x.l/B<y.l/B;
        return x.l/B&1 ? x.r>y.r:x.r<y.r;
    });
    int l=1,r=1,cnt=1;
    on[a[1]].flip();
    for(int i=1;i<=m;i++){
        while(l>q[i].l) on[a[--l]].flip(),cnt+=on[a[l]] ? 1:-1;
        while(r<q[i].r) on[a[++r]].flip(),cnt+=on[a[r]] ? 1:-1;
        while(l<q[i].l) on[a[l++]].flip(),cnt+=on[a[l-1]] ? 1:-1;
        while(r>q[i].r) on[a[r--]].flip(),cnt+=on[a[r+1]] ? 1:-1;
        ans[q[i].i]=(cnt==0);
    }
    for(int i=1;i<=m;i++) puts(ans[i] ? "Yes":"No");
    for(int i=1;i<=n;i++) if(on[a[i]]) on[a[i]]=0;
}
int T;
int main(){
    scanf("%d",&T);
    while(T--) solution();
    return 0;
}

Solution 2：需要一种符合交换律的方法判断所有值是否都出现了偶数次，可以使用异或哈希维护。给每个数赋一个哈希权值后判断区间异或和是否为 $0$ 即可。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
unsigned long long sum[200'005],w[1'000'005];
int n,m;
mt19937_64 sky(time(0));
void solution(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        static int x;
        scanf("%d",&x);
        if(!w[x]) w[x]=sky();
        sum[i]=sum[i-1]^w[x];
    }
    for(int i=1;i<=m;i++){
        static int l,r;
        scanf("%d%d",&l,&r);
        puts(sum[r]^sum[l-1] ? "No":"Yes");
    }
}
int T;
int main(){
    scanf("%d",&T);
    while(T--) solution();
    return 0;
}