暑假考试题3：jigsaw 黄金拼图（乱搞）

考试题3：jigsaw 黄金拼图（乱搞）"/>

暑假考试题3：jigsaw 黄金拼图（乱搞）

题目：

分析：

不满足的拼图其实就是素数，这道题乍一看，诶这不是强制在线带修改的区间第K小吗？怎么这种毒瘤树套树会出在T1？？？

结果。。。仔细读题，会发现一些小细节：opt都要通过异或上一次的答案才能得到，这不免有些蹊跷。。。然后所有答案都是为奇数的素数

再考虑异或的性质：ans的二进制位最后一位一定是1，opt ^ lastans会得到1或2 ， 而1最后一位是1，2最后一位是0

如果给出的opt是奇数，那么一定是lastans ^ opt==2，又opt已知，那么lastans不就求出来了吗？？？

所以说对于每一个询问，都可以通过下一个给出的opt反推出来！！！

最后一个询问暴力求一下就好了。

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define M 1000005
int a[N],pri[M],su[M],k,tmp[N],cnt=0;
int read()
{/*int x=0,fl=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') fl=-1; ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*fl;*/int x;scanf("%d",&x);return x;
}
void suu()
{int nn=M-5;for(int i=2;i<=nn;i++){if(!pri[i]) su[++cnt]=i;for(int j=1;j<=cnt&&su[j]*i<=nn;j++){pri[su[j]*i]=1;if(i%su[j]==0) break;}}
}
int query(int l,int r)
{int tot=0;for(int i=l;i<=r;i++) if(!pri[a[i]]) tmp[++tot]=a[i];sort(tmp+1,tmp+1+tot);return tmp[k];
}
int main()
{freopen("jigsaw.in","r",stdin);freopen("jigsaw.out","w",stdout);int n,m,opt,l,r;suu();n=read(); k=read(); m=read();for(int i=1;i<=n;i++) a[i]=read();int fl=0,last=0;for(int i=1;i<=m;i++){opt=read(); l=read(); r=read();if(fl){if(!(opt&1)) last=opt^1,printf("%d\n",last);else last=opt^2,printf("%d\n",last);fl=0;}opt^=last; l^=last; r^=last;if(opt==1) fl=1;else a[l]=r;}if(fl) printf("%d\n",query(l,r));
}
/*
5 2 4
11 4 6 3 5
2 2 3
1 1 4
1 1 7
2 2 73 1 3
4 5 6
1 1 3
7 7 2
4 4 63 2 3
4 5 7
1 1 3
5 4 2
6 6 45 2 4
3 2 6 7 5
1 1 4
2 2 4
1 1 4
1 1 5*/

转载于:.html