正文
[hdu7035]Game
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
称区间$[i,j]$为普通区间，当且仅当$j-i\ge 3$且其操作两次内不会变为给定区间
结论： 若$[i,j]$为普通区间，则$[i,j]$和$[i+1,j-1]$的状态（是否先手必胜）相同
（关于这个结论的正确性，不难分类讨论得到）
由此，对于普通区间不断缩小使其变为非普通区间，而非普通区间暴力枚举其变化，直至其长度为1或变为普通区间，显然这类区间至多只有$o(n)$个，因此记忆化后总复杂度也为$o(n)$
综上，只需要能快速实现缩小的过程即可，注意到和是相同的，以和为第一关键字，左端点为第二关键字在所有第2类的非普通区间中二分即可
（暴力的过程中判定区间是否为特殊区间也可以二分）
最终，总复杂度为$o((n+q)\log n)$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 600005
4 int t,n,m,q,l,r,ans[N];
5 struct Data{
6 int l,r,p;
7 bool operator < (const Data &k)const{
8 return (l+r<k.l+k.r)||(l+r==k.l+k.r)&&(l<k.l);
9 }
10 bool operator == (const Data &k)const{
11 return (l==k.l)&&(r==k.r);
12 }
13 bool operator != (const Data &k)const{
14 return (l!=k.l)||(r!=k.r);
15 }
16 }a[N],b[N];
17 int find(int l,int r){
18 Data o=Data{l,r,0};
19 int p=lower_bound(b+1,b+m+1,o)-b;
20 if ((p>m)||(b[p]!=o))return -1;
21 return p;
22 }
23 int get_nex(int l,int r){
24 Data o=Data{l,r,0};
25 int p=lower_bound(b+1,b+m+1,o)-b;
26 if ((p<=m)&&(o.l+o.r==b[p].l+b[p].r))return b[p].l-o.l;
27 return (r-l-1>>1);
28 }
29 bool calc(int l,int r){
30 int p=find(l,r);
31 if (p>0){
32 if (b[p].p>=0)return b[p].p;
33 if (ans[p]>=0)return ans[p];
34 }
35 if (l==r)return 0;
36 if ((r-l>=3)&&(p<0)){
37 p=get_nex(l,r);
38 return calc(l+p,r-p);
39 }
40 int s=((calc(l,r-1)&calc(l+1,r))^1);
41 if (p>0)ans[p]=s;
42 return s;
43 }
44 int main(){
45 scanf("%d",&t);
46 while (t--){
47 scanf("%d%d",&n,&q);
48 for(int i=1;i<=n;i++){
49 scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].p);
50 a[i+n]=Data{a[i].l-1,a[i].r,-1};
51 a[i+n*2]=Data{a[i].l-2,a[i].r,-1};
52 a[i+n*3]=Data{a[i].l,a[i].r+1,-1};
53 a[i+n*4]=Data{a[i].l,a[i].r+2,-1};
54 a[i+n*5]=Data{a[i].l-1,a[i].r+1,-1};
55 }
56 sort(a+1,a+n*6+1);
57 m=0;
58 for(int i=1;i<=n*6;i++){
59 if ((a[i].l<=0)||(a[i].r>1e9))continue;
60 if ((!m)||(b[m]!=a[i]))b[++m]=a[i];
61 else{
62 if (b[m].p<0)b[m].p=a[i].p;
63 }
64 }
65 for(int i=1;i<=m;i++)ans[i]=-1;
66 for(int i=1;i<=q;i++){
67 scanf("%d%d",&l,&r);
68 printf("%d",calc(l,r));
69 }
70 printf("\n");
71 }
72 return 0;
73 }
