【DBSDFZOJ 4415】黄金拼图（乱搞）

拼图（乱搞）"/>

【DBSDFZOJ 4415】黄金拼图（乱搞）

Description

九条可怜有 n 盒拼图，每盒拼图都有若干拼图块，可以拼出许多矩形图案。可是，可怜经常会弄丢拼图块，因此她需要将一些拼图送回厂家进行补块。可怜懒得将所有拼图拼好来检查完整性，仅当她的一盒拼图的拼图块数无法组成任何 r 块×c 块的矩形图案（其中 r,c≥2），可怜才认为这盒拼图需要返厂补块。返厂补块需要的运费只和含有图块数最多的拼图有关。
可怜将 n 盒拼图从 1 到 n 编号。每次，可怜都想知道，如果从编号在[l,r]区间内的拼图中选择 k 盒一定需要补块的拼图，拼图块数最多的拼图的拼图块数最少是多少。当然，可怜只是随口问问，并不会真的将这些拼图返厂，所以询问后所有拼图的块数都不会变化。
有时，可怜会发现自己数错了拼图的块数，并将第 x 盒拼图的拼图块数更新为 y。她希望你能即时回答这些询问。

Input

第一行两个整数 n,k,m，m 表示可怜询问和修改的数量和。
接下来一行 n 个正整数，第 i 个数表示第 i 盒拼图初始时的拼图块数。
接下来 m 行，每行 3 个数 opt,l,r。为了表明你在即时回答可怜的询问，真实的 opt,l,r 为输入的 opt,l,r 分别异或（XOR）lastans，其中 lastans 表示上一次询问的答案，若之前没有询问操作，则 lastans=0。
若opt=1，则表示这是一次询问操作，询问的区间为[l,r]。
若opt=2，则表示这是一次修改操作，把第 l 盒拼图的块数修改为 r。

Output

对于每个询问操作，输出一行一个整数，表示拼图块数最多的拼图的拼图块数最少是多少。保证答案存在。

Sample Input 1

3 1 3
4 5 6
1 1 3
7 7 2
4 4 6

Sample Output 1

5
7

Sample Input 2

3 2 3
4 5 7
1 1 3
5 4 2
6 6 4

Sample Output 2

7
5

Data Constraint

对于 30%的数据，n,m≤1000。
对于另 30%的数据，没有修改操作。
对于 100%的数据，1≤n,m,k≤200000，l,r 合法，所有拼图的块数在任何时刻是[4,1000000]区间中的整数。

解题思路

这题看起来是不是很高端啊，是不是像什么高端的平衡树之类的数据结构啊
可是这题你要是按题目描述说的那样计算你就输了。
正解乱搞：我们可以发现 lastans 一定是一个大于4的质数，因此lastans的二进制最低位一定是 1。由于opt是1或者2，所以可以根据opt的奇偶性判定lastans的值。反解出答案后只有最后一个操作是询问时需要暴力处理，预处理出质数后将最后一个询问的区间排序后暴力查询就可以了。
复杂度 O(v log v) ，其中 v 表示值域。若使用线性筛，可以做到复杂度 O(v) 。

代码

#include<bits/stdc++.h>
#define V 1000000
#define N 200000
using namespace std;
bool isprime[V+1];
int a[N+5],b[N+5];
int n,m,k,ans=0;
bool pre=false;
inline void getprime(){memset(isprime,true,sizeof(isprime));for(int i=2;i<=V;++i)if(isprime[i]){for(int j=i<<1;j<=V;j+=i)      isprime[j]=false;}
}
int search(int l,int r){int p=0;for(int i=l;i<=r;++i)if(isprime[a[i]])   b[++p]=a[i];sort(b+1,b+p+1);return b[k];
}
int main(){scanf("%d%d%d",&n,&k,&m);getprime();for(int i=1;i<=n;++i)     scanf("%d",&a[i]);int opt,l,r;for(int i=1;i<=m;++i){scanf("%d%d%d",&opt,&l,&r);if(pre){ans=opt&1?opt^2:opt^1;pre=false;printf("%d\n",ans);}opt^=ans;l^=ans;r^=ans;if(opt==1)      pre=true;else            a[l]=r;}if(opt==1)      printf("%d",search(l,r));return 0;
}