一、题目
二、解法
本来想刷数据结构题的，结果跳到一道思维题做 \(\tt nm\) 一晚上。
因为只有两堆石子所以我们把它放在二维平面上方便分析，然后每个位置我们标上 \(0/1\) 表示这个状态是必胜还是必败，根据 \(\tt nim\) 游戏的知识 \(n=0\) 时只有 \(x=y\) 这些点时必败的。
没有什么好的思路，那么我们手玩一下 \(n=1\) 的情况，考虑添加一个 \((a,b)\) 的必败态：
根据上面的图我们可以知道添加 \(1\) 个点的影响如下：
- 如果 \(a>b\)，那么 \((a,a)\) 会变为必胜态，\((a+1,a)\) 会变为必败态，必败态直线向右平移。
- 如果 \(a<b\)，那么 \((b,b)\) 会变为必胜态，\((b,b+1)\) 会变为必败态，必败态直线往上平移。
那么添加多个点也可以类似地推导出来，设必败态直线 \(x=y+d\)
- 如果 \(a>b+d\)，也就是该点在必败态直线的下方，\(d\) 加 \(1\)
- 如果 \(a<b+d\)，也就是该点在必败态直线的上方，\(d\) 减 \(1\)
那么我们维护必败态直线即可，把点和询问都按 \(x\) 为第一关键字，\(y\) 为第二关键字离线，最后必败态直线可能是分段的（跟 \(y\) 有关），所以我们维护一个关于 \(y\) 的树状数组处理 \(d\) 减 \(1\) 的影响。
最后就是要判断 \(x/y\) 相等的情况，如果 \(x\) 相等那么只能让 \(d\) 加 \(1\) 进行一次，如果 \(y\) 相等那么也只能让 \(d\) 减 \(1\) 进行一次，更多细节参考代码吧。
三、总结
当没有思路时，从简单的情况推起！
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 200005;
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,k,t,nx,cx,ans[M],a[M],b[M],f[M];
struct node
{
int x,y,id;
bool operator < (const node &b) const
{
if(x!=b.x) return x<b.x;
if(y!=b.y) return y<b.y;
return id<b.id;
}
}s[M];
int lowbit(int x)
{
return x&(-x);
}
void add(int x)
{
for(int i=x;i<=t;i+=lowbit(i))
b[i]++;
}
int ask(int x)
{
int r=0;
for(int i=x;i>=1;i-=lowbit(i))
r+=b[i];
return r;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
s[++k].x=read(),s[k].y=read(),a[i]=s[k].y;
for(int i=1;i<=m;i++)
s[++k].x=read(),s[k].y=read(),s[k].id=i;
sort(s+1,s+1+k);
sort(a+1,a+1+n);
t=unique(a+1,a+1+n)-a-1;
for(int i=1;i<=k;i++)
{
if(s[i].id)//query
{
if(!s[i-1].id && s[i-1].x==s[i].x && s[i-1].y==s[i].y)
ans[s[i].id]=1;
else if(s[i].x!=nx)
{
int y=upper_bound(a+1,a+1+t,s[i].y)-a-1;
if((s[i].y!=a[y] || !f[y]) && s[i].x==s[i].y+cx-ask(y))
ans[s[i].id]=1;
}
continue;
}
int y=lower_bound(a+1,a+1+t,s[i].y)-a,d=cx-ask(y);
if(s[i].x<s[i].y+d && !f[y])
f[y]=1,add(y);
if(s[i].x>s[i].y+d && nx!=s[i].x)
cx++,nx=s[i].x;
}
for(int i=1;i<=m;i++)
if(!ans[i]) puts("WIN");
else puts("LOSE");
}