分析题目性质好题！
无法组成r*c（r，c>=2）说明是质数或者1才是满足条件的拼图。
看数据范围，前30%暴力可以做，另30%不带修改即是主席树，那么带修改就是树套树？？？
然鹅并不是，树套树会T（然鹅我并不会打树套树）
我们发现ans保证是在[4，1000000]，那么
lastans一定是一个大于4的质数，因此lastans的二进制最低位一定是1。
由于opt是1或者2，所以可以根据opt的奇偶性判定lastans的值。
反解出答案后只有最后一个操作是询问时需要暴力处理。预处理出质数后将最后一个询问的区间排序后暴力查询即可。
因为每一次处理的ans都是前面的而不是本次的，如果最后的操作为1，就只能暴力处理，后面没有op来给它判断了。
使用线性筛时间可做到O（n）。
#include<bits/stdc++.h> #define N 200003 #define INF 1000002 using namespace std; bool notp[1000005]; int tot=0,prime[500000]; int a[N],tmp[N]; int k,p=0; int read() { int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } void init() { for(int i=2;i<=1000003;++i) { if(!notp[i])prime[++tot]=i; for(int j=1;j<=tot&&i*prime[j]<=1000003;++j) { notp[i*prime[j]]=1; if(i%prime[j]==0)break; } } } int main() { freopen("jigsaw.in","r",stdin); freopen("jigsaw.out","w",stdout); init(); int n=read();k=read();int m=read(); for(int i=1;i<=n;i++) a[i]=read(); int ans=0; int op,l,r; int pre=0; for(int i=1;i<=m;i++) { op=read();l=read();r=read(); if(pre)//用pre判断前面是否有没有输出的答案 ,而不是看i是否等于1，因为可能前面有很多2操作 { ans=(op&1)?op^2:op^1;//这一次的op是奇数，而当前的ans质数也是奇数，^之后一定是2（二进制为10）,否则为1 pre=0;//ans^op=1--->ans=op^1 , ans^op=2--->ans=op^2 printf("%d\n",ans); } op^=ans; l^=ans;r^=ans; if(op==1) pre=1;//记录还有一次没输的答案 else a[l]=r; } if(op==1)//最后一次暴力就可做 { p=0; for(int i=l;i<=r;++i) if(!notp[a[i]])tmp[++p]=a[i]; sort(tmp+1,tmp+1+p); printf("%d\n",tmp[k]); } } /* 3 1 3 4 5 6 1 1 3 7 7 2 4 4 6 */
2019暑假集训8.24（problem1.jigsaw）（乱搞/分析题目性质）
原文：https://www.cnblogs.com/yyys-/p/11405608.html
