一、题目
有 (n) 个人排成环，第 (i) 个人有 (a_i) 张卡牌，属于阵营 (t_i)，首先第一个人会打出卡牌，然后和当前打出卡牌的人属于不同阵营且距离它最近（向右的距离）的人会接着打出卡牌。
问每个人最后的卡牌数，输入和输出都需要按题目所述进行加密。
(nleq 5cdot 10^6)
二、解法
首先做一些基本的观察：所属阵营卡牌总数少的阵营都是 (0)
然后考虑打牌的形式是从序列上选取一个环，然后环上每个人依次打牌之后有人无牌退出游戏。这相当于每次删去环上的最小值，我们考虑维护这个环：
- 考虑删除的位置是 (id)，如果下一个位置同色则在环上替换成下一个位置。
- 如果下一个位置异色，那么它在环上的前驱需要把它在环上的后继的同色段合并起来。
感觉暴力维护的话需要 ( t set/priority) 之类的数据结构，(O(nlog n)) 无法通过。
但是没有必要按照时间顺序来维护环，我们考虑一个很小的局部问题，对于相邻两个属于不同阵营的人，当它们出现在环上时，可以看成它们"决斗"之后其中一个挂掉。
我们钦定起点属于总数少的阵营（否则我们暴力先跳一步），然后从它开始线性扫，如果遇到相同阵营的就让 (cntleftarrow cnt+a_i)，如果遇到不同阵营的就让它和 (cnt) "决斗"，显然这样做是把我上面说的巧妙地模拟了出来，时间复杂度 (O(n))
三、总结
不只是此题，很多题目简化实现(/)优化复杂度的关键都是减少我们维护的量，我们可以遵守一个 整体->局部 的思维过程，先考虑整体的变化再反映到局部上便于快速计算。
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int N = 200005;
const int M = 5000005;
const int MOD = 1e9+7;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,cnt,ans,seed,base,sum[2],a[M],tmp[M],t[M];
int random()
{
int ret=seed;
seed=(seed*base+233)%MOD;
return ret;
}
void decode()
{
n=read();m=read();
for(int i=1,ls=0;i<=m;i++)
{
int p=read(),k=read(),b=read(),w=read();
seed=b;base=w;
for(int j=ls+1;j<=p;j++)
{
t[j]=random()%2;
a[j]=random()%k+1;
}
ls=p;
}
}
signed main()
{
decode();
for(int i=1;i<=n;i++)
sum[t[i]]+=a[i],tmp[i]=a[i];
int st=1,nw=1;
if(sum[t[1]]>sum[!t[1]])//switch the start pos
{
sum[t[1]]--;a[1]--;
while(st<=n && t[st]==t[1]) st++;
}
nw=st;
if(st<=n) while(sum[t[st]]>0)
{
if(t[nw]==t[st])
cnt+=a[nw],a[nw]=0;
else
{
int o=min(cnt,a[nw]);
a[nw]-=o;cnt-=o;sum[t[st]]-=o;
}
nw=nw%n+1;
}
ans=1;
for(int i=1;i<=n;i++)
ans=ans*((((tmp[i]-a[i])^(i*i))+1)%MOD)%MOD;
printf("%lld
",ans);
}