杭电多校第三场-H-Game

题目描述

Again Alice and Bob is playing a game with stones. There are N piles of stones labelled from 1 to N, the i th pile has ai stones. 

First Alice will choose piles of stones with consecutive labels, whose leftmost is labelled with L and the rightmost one is R. After, Bob will choose another consecutive piles labelled from l to r (L≤l≤r≤R). Then they're going to play game within these piles.

Here's the rules of the game: Alice takes first and the two will take turn to make a move: choose one pile with nonegetive stones and take at least one stone and at most all away. One who cant make a move will lose.

Bob thinks this game is not so intersting because Alice always take first. So they add a new rule, which is that Bob can swap the number of two adjacent piles' stones whenever he want before a new round. That is to say, if the i th and i+1 pile have ai and ai+1 stones respectively, after this swapping there will be ai+1 and ai.

Before today's game with Bob, Alice wants to know, if both they play game optimally when she choose the piles from L to R, there are how many pairs (l, r) chosed by Bob that will make Alice *win*.

输入

Input contains several test cases.

For each case:

The fisrt line contains N, M. N is mentioned aboved ans M is the number of the sum of game rounds and the times of Bob's swapping.

The second line contains N integars a1,a2,...an, indicating the number of each piles' stones.

The next M lines will have an integar opt (1≤opt≤2), indicating the type of operation.

If opt equals 1, then L and R follow. Alice and Bob start a new round and Alice choose L and R as mentioned. 

If opt equals 2, then POS follows. Bob will swap the piles labelled POS and POS+1.

0≤ai≤1,000,000

1≤N,M≤100,000,∑N,∑M<600,000

1≤L≤R≤N

1≤POS<N

输出

For each case:

For each opt which equals 1, you shall output one line with an integar indicating the number of pairs (l,r) that will make Alice win the round. 题意： 看起来是个博弈，但是分析下来发现题意就是让你找[L,R]区间内有多少个[l,r]满足al^a(l+1)^...^ar！=0，那不就是莫队吗 然后发现还要支持修改，每次选择一个位置pos，将a[pos]和a[pos+1]交换 那不就不会了吗三维莫队，即带修改的莫队 在普通的莫队上增加一维版本号，对询问排序时，先按块排，再按版本号排 更新的时候，先更新版本，再更新区间 #include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+10; int T,n,m; int block; ll tot; struct orz{int l,r,t,id;bool operator < (const orz &x) const{if (l/block==x.l/block){if (r/block==x.r/block) return t<x.t;return r<x.r;}return l/block<x.l/block;} }p[N]; int a[N],val[N],c[N],sum[N*2]; ll ans[N]; inline int read() {int x=0;char ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x; } void Go(int l,int r,int i) {int pos=c[i]; //cout<<pos<<endl;if (pos>=l&&pos<=r){sum[val[pos]]--;tot-=sum[val[pos]];}val[pos]^=a[pos]; val[pos]^=a[pos+1];if (pos>=l&&pos<=r){tot+=sum[val[pos]];sum[val[pos]]++;}swap(a[pos],a[pos+1]);//for (int i=1;i<=n;i++) cout<<val[i]<<' '; cout<<endl; }void add(int x) {tot+=sum[x];sum[x]++; } void del(int x) {sum[x]--;tot-=sum[x]; } int main() {// freopen("00.in","r",stdin);// freopen("1.out","w",stdout);while (scanf("%d%d",&n,&m)!=EOF){int ti=0,cnt=0;for (int i=1;i<=n;i++) a[i]=read(),val[i]=val[i-1]^a[i];//for (int i=1;i<=n;i++) cout<<val[i]<<' '; cout<<endl;int op,x,y;for (int i=1;i<=m;i++){op=read();if (op==1){x=read(); y=read();p[++cnt].l=x-1; p[cnt].r=y; p[cnt].t=ti; p[cnt].id=cnt;}else{c[++ti]=read();}}block=pow(n,2.0/3.0);sort(p+1,p+1+cnt);// sum[0]++;int l=1,r=0,t=0; tot=0;for(int i=1;i<=cnt;i++){while (t<p[i].t) Go(l,r,++t);while (t>p[i].t) Go(l,r,t--);//cout<<t<<endl;while (l>p[i].l) add(val[--l]);while (l<p[i].l) del(val[l++]);while (r<p[i].r) add(val[++r]);while (r>p[i].r) del(val[r--]);ll len=p[i].r-p[i].l; //cout<<len<<' '<<tot<<endl;ans[p[i].id]=len*(len-1)/2+len-tot;}for (int i=1;i<=cnt;i++) printf("%lld\n",ans[i]);for (int i=1;i<=n;i++) sum[val[i]]=0;}// fclose(stdin);// fclose(stdout);return 0; } View Code

 

转载于:https://www.cnblogs.com/tetew/p/11268471.html

总结

以上是生活随笔为你收集整理的杭电多校第三场-H-Game的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。