icontofig | 发布于 2019-07-30 12:14:20 | 阅读量 294 | 莫队 博弈论 NIM博弈
发布于 2019-07-30 12:14:20 | 莫队 博弈论 NIM博弈

题目大意

先手选出区间L-R的连续的石子堆,后手可以交换第pos 和 pos+1堆石子,然后再从L-R选出区间l-r的石子两人进行取石子博弈。

问在L-R中有多少种后手取l-r的方案能够使得先手必胜。

题解

这题是一个经典的NIM博弈。我们需要用SG函数来解决。

我们考虑前缀SG函数异或和,区间L-R内有多少选择l-r的方案使得先手必胜这一点我们可以转化为有都少方案使得先手必败(SG函数异或和为0)

l-r的SG函数异或和为0,即前缀异或和ssg满足ssg[r] = ssg[l-1],问题转化为统计区间中有多少ssg相等的点对数。

然后我们使用区间点对总数减去区间中ssg相等的点对数就是当前询问的答案。点对问题我们通常使用莫队的分治思想来处理。

然而此题还有交换石子堆的操作,我们能够发现,交换实际上只对一个前缀异或和有影响,所以交换操作实际上就是一个单点修改。

于是我们使用带修改莫队处理整个题目。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
int n,m;
struct query{
    int l,r,t,id;
}q[maxn];
int belong[maxn];
int upd[maxn];
int qcnt,dcnt;
int a[maxn],b[maxn];
int num[2000005];
int lp;
bool cmp(query x,query y){
    return x.l/lp == y.l/lp ? (x.r/lp == y.r/lp ? x.t < y.t : x.r < y.r) : x.l < y.l;
}
int x;
int opt;
ll sum;
ll ans[maxn];
void del(int x){
    sum -= --num[x];
    return;
}
void add(int x){
    sum += num[x]++;
    return;
}
void update(int i,int t){
    if(q[i].l <= upd[t] && upd[t] <= q[i].r)
        del(b[upd[t]]);
    b[upd[t]] ^= a[upd[t]];
    swap(a[upd[t]],a[upd[t]+1]);
    b[upd[t]] ^= a[upd[t]];
    if(q[i].l <= upd[t] && upd[t] <= q[i].r)
        add(b[upd[t]]);
}
int main(){
    while(scanf("%d%d",&n,&m) != EOF){
        for(int i = 1;i <= n;++i){
            a[i] = get_num();
            b[i] = b[i-1]^a[i];
        }
        sum = 0;
        qcnt = dcnt = 0;
        memset(num,0,sizeof(num));
        lp = max(10,(int)pow(n,2.0 / 3));
        for(int i = 1;i <= m;++i){
            opt = get_num();
            if(opt == 1){
                q[++qcnt].l = get_num() - 1;
                q[qcnt].r = get_num();
                q[qcnt].id = qcnt;
                q[qcnt].t = dcnt;
            }
            if(opt == 2){
                x = get_num();
                upd[++dcnt] = x;
            }
        }
        sort(q+1,q+qcnt+1,cmp);
        int l = 0,r = -1,now = 0;
        for(int i = 1;i <= qcnt;++i){
            while(l < q[i].l){
                del(b[l]);
                l++;
            }
            while(l > q[i].l){
                l--;
                add(b[l]);
            }
            while(r < q[i].r){
                r++;
                add(b[r]);
            }
            while(r > q[i].r){
                del(b[r]);
                r--;
            }
            while(now < q[i].t){
                now++;
                update(i,now);
            }
            while(now > q[i].t){
                update(i,now);
                now--;
            }
            ans[q[i].id] = 1ll * (r - l + 1) * (r - l) / 2 - sum;
        }
        for(int i = 1;i <= qcnt;++i){
            printf("%lld\n",ans[i]);
        }
    }
    return 0;
}

 


内容更新于: 2019-08-03 20:58:31
链接地址: http://blog.leanote.com/post/icontofig/9fd631b57204

上一篇: 主席树模板

下一篇: 2019 Multi-University Training Contest 1 1002 Operation 线性基

294 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航