重庆建设行政主管部门网站,如何做旅游攻略网站,沈阳seo合作,哈尔滨百度网络推广题目大意
有 n n n个数字#xff0c;第 i i i个数字为 a i a_i ai。有 m m m次询问#xff0c;每次给出 k i k_i ki个区间#xff0c;每个区间表示第 l i , j l_{i,j} li,j到第 r i , j r_{i,j} ri,j个数字#xff0c;求这些区间中一共出现了多少种不同的数字。部…题目大意
有 n n n个数字第 i i i个数字为 a i a_i ai。有 m m m次询问每次给出 k i k_i ki个区间每个区间表示第 l i , j l_{i,j} li,j到第 r i , j r_{i,j} ri,j个数字求这些区间中一共出现了多少种不同的数字。部分数据强制在线。
时限1s空间8MB。
输入格式
第一行包括三个整数 n , m , p n,m,p n,m,p p p p为 0 0 0或 1 1 1表示是否强制在线。
第二行 n n n个正整数第 i i i个表示 a i a_i ai。
接下来依次给出每个询问每个询问第一行一个正整数表示 k i k_i ki。接下来 k i k_i ki行每行两个正整数分别表示 l i , j l_{i,j} li,j和 r i , j r_{i,j} ri,j。
若 p 1 p1 p1且这不是第一个询问则输入的 l i , j l_{i,j} li,j和 r i , j r_{i,j} ri,j是经过加密的你需要将这两个数字分别异或上上一个询问的答案对 n n n取模后再加 1 1 1两者的较小值为真实的 l i , j l_{i,j} li,j较大值为真实的 r i , j r_{i,j} ri,j。
输出格式
对每个询问输出一行一个整数表示答案。
输入样例
3 2 0
1 2 1
1
1 2
2
1 1
3 3输出样例
2
1数据范围 1 ≤ n , m , ∑ k i , a i ≤ 1 0 5 , 1 ≤ l i , j ≤ r i , j ≤ n 1\leq n,m,\sum k_i,a_i\leq 10^5,1\leq l_{i,j}\leq r_{i,j}\leq n 1≤n,m,∑ki,ai≤105,1≤li,j≤ri,j≤n 题解
首先我们考虑 p 0 p0 p0的情况。
我们可以用 b i t s e t bitset bitset来维护每个点是否出现。先把各个区间离线下来用莫队求出每个区间的 b i t s e t bitset bitset。把每个询问并起来。这样做的时间复杂度为 O ( n n n m 64 ) O(n\sqrt n\dfrac{nm}{64}) O(nn 64nm)。
空间开不下我们考虑优化。
既然要用 b i t s e t bitset bitset那么时间复杂度肯定是要带 n m 64 \dfrac{nm}{64} 64nm的了。我们不妨将每 n 64 \dfrac{n}{64} 64n个元素分一块对于每次询问非整块的暴力处理再预处理整块到整块的 b i t s e t bitset bitset即可。
空间开不下就对这 64 64 64个块建 S T ST ST表。建 S T ST ST表不用倍增对每种长度从左到右推一遍即可。
在优化一下常数。只出现过一次的权值把它们单独求一个前缀和每次特殊处理即可。这样的话每个权值至少出现两次离散化之后权值个数能减少至少一半。
离散化的时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)建 S T ST ST表的时间复杂度为 O ( n log 64 ) O(n\log 64) O(nlog64)查询的时间复杂度为 O ( n m 64 64 n ) O(\dfrac{nm}{64}64n) O(64nm64n)总时间复杂度为 O ( n m 64 ) O(\dfrac{nm}{64}) O(64nm)。因为权值个数减半所以时间复杂度能降低到 O ( n m 128 ) O(\dfrac{nm}{128}) O(128nm)。
空间复杂度为 O ( n log 64 ) O(n\log 64) O(nlog64)。
这道题有一定的思维难度可以结合代码帮助理解。
code
#includebits/stdc.h
#define N 100032
#define K 1563
#define Z 782
using namespace std;
int n,m,p,c10,lst,ans,a[N5],s[116],t[105],c[N5],sum[N5];
struct pt{unsigned long long z[Z];void set(int x){z[x6]|1ull(x63);}void rev(int x){z[x6]^1ull(x63);}int count(){int re0;for(int i0;iZ;i){res[z[i]48]s[(z[i]32)65535]s[(z[i]16)65535]s[z[i]65535];}return re;}
}v,b[6][70];//按颜色分成64块
struct node{int l,r;
}w[N5];
bool cmp(node ax,node bx){if(ax.l!bx.l) return ax.lbx.l;return ax.rbx.r;
}
void kuai(int l,int r){if(lr) return;int xt[r-l1];for(int i0;iZ;i){v.z[i]|b[x][l].z[i]|b[x][r-(1x)1].z[i];}
}//所有大块处理
void dd(int l,int r){if((l-1)/K(r-1)/K){for(int il;ir;i) v.set(a[i]);}else{for(int il;i(l-1)/K*KK;i) v.set(a[i]);kuai((l-1)/K1,(r-1)/K-1);for(int i(r-1)/K*K1;ir;i) v.set(a[i]);}
}//分块
int main()
{scanf(%d%d%d,n,m,p);for(int i2;i64;i) t[i]t[i1]1;for(int i1;i116;i) s[i]s[i1](i1);for(int i1;in;i){scanf(%d,a[i]);c[a[i]];}for(int i1;in;i){sum[i]sum[i-1];if(c[a[i]]1){a[i]0;sum[i];}}//若只出现过一次放到前缀和数组中for(int i1;in;i){if(a[i]) c[c1]a[i];}sort(c1,cc11);c1unique(c1,cc11)-c-1;for(int i1;in;i){if(a[i]){a[i]lower_bound(c1,cc11,a[i])-c;}}//离散化for(int i0,xK;i6;i,x1){memset(v.z,0,sizeof(v.z));memset(c,0,sizeof(c));for(int j1;jx;j){if(!c[a[j]]) v.rev(a[j]);c[a[j]];}b[i][0]v;for(int jK;jxN;jK){for(int k0;kK;k){if(!c[a[jx-k]]) v.rev(a[jx-k]);c[a[jx-k]];--c[a[j-k]];if(!c[a[j-k]]) v.rev(a[j-k]);}b[i][j/K]v;}//按位置分成64块}//ST表for(int o1,k,l,r;om;o){ans0;memset(v.z,0,sizeof(v.z));scanf(%d,k);for(int i1;ik;i){scanf(%d%d,w[i].l,w[i].r);if(po1){w[i].l(w[i].l^lst)%n1;w[i].r(w[i].r^lst)%n1;if(w[i].lw[i].r) swap(w[i].l,w[i].r);}}sort(w1,wk1,cmp);lw[1].l;rw[1].r;for(int i2;ik;i){if(w[i].lr1){anssum[r]-sum[l-1];dd(l,r);lw[i].l;}rmax(r,w[i].r);}anssum[r]-sum[l-1];dd(l,r);//合并区间ansv.count()-(v.z[0]1);//z[0]的第一个位置是为0的a值不统计lstans;printf(%d\n,ans);//求答案}return 0;
}
