摘要：
仔细阅读问题，你会发现一些小细节：opt只能通过互斥或最后一个答案获得，这有点奇怪……所以对于每个查询，你可以使用下一个给定的opt来推导！！！
题目：
分析：
不满足的拼图其实就是素数，这道题乍一看，诶这不是强制在线带修改的区间第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 ",last); else last=opt^2,printf("%d ",last); fl=0; } opt^=last; l^=last; r^=last; if(opt==1) fl=1; else a[l]=r; } if(fl) printf("%d ",query(l,r)); } /* 5 2 4 11 4 6 3 5 2 2 3 1 1 4 1 1 7 2 2 7 3 1 3 4 5 6 1 1 3 7 7 2 4 4 6 3 2 3 4 5 7 1 1 3 5 4 2 6 6 4 5 2 4 3 2 6 7 5 1 1 4 2 2 4 1 1 4 1 1 5 */