c 网站开发的书籍,google官网登录入口,企业解决方案榜单,宁波seo怎么做优化公司传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个长度为nnn的数组#xff0c;每次询问l,r,a,bl,r,a,bl,r,a,b代表询问[l,r][l,r][l,r]区间内有多少个不同的数x⊕a≤bx\oplus a\le bx⊕a≤b。 n≤1e5,a,b,x≤n1n\le1e5,a,b,x\le n1n≤1e5,a,b,x≤n1…传送门
文章目录题意思路题意
给你一个长度为nnn的数组每次询问l,r,a,bl,r,a,bl,r,a,b代表询问[l,r][l,r][l,r]区间内有多少个不同的数x⊕a≤bx\oplus a\le bx⊕a≤b。 n≤1e5,a,b,x≤n1n\le1e5,a,b,x\le n1n≤1e5,a,b,x≤n1
思路
先不考虑区间限制且不考虑不同的数单纯的求数量考虑如何求出x⊕a≤bx\oplus a\le bx⊕a≤b的个数。 显然可以开一颗tiretiretire树将所有xxx插入让后在tiretiretire树上分情况走即可简单来说就是尽可能走每一位等于bbb的当前位的位置对于另一个位置看情况统计答案即可。 对于求不同的数有多少个这是个经典问题我们维护每个数最后一次出现的位置每次用树状数组查询[1,r]−[1,l−1][1,r]-[1,l-1][1,r]−[1,l−1]的数量即可。 对于有区间限制且需要求不同数的个数我们可以将上面的两个思路结合起来简单来说就是考虑建nnn棵tiretiretire树用树状数组实现快速修改以及查询每次都修改和查询是log2log^2log2的复杂度。 复杂度O(nlog2n)O(nlog^2n)O(nlog2n)
// Problem: D - I love counting
// Contest: Virtual Judge - 2021多校第二场补题
// URL: https://vjudge.net/contest/448870#problem/D
// Memory Limit: 262 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
#define lowbit(x) x(-x)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N100010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int a[N],pre[N],ans[N];
int st[N];
struct Node {int l,id,a,b;
};
vectorNodev[N];
int tree[N];int tr[N*300][2],cnt[N*100],idx;void insert(int x,int now,int tag) {if(!now) nowidx;int pnow;for(int i18;i0;i--) {int uxi1;if(!tr[p][u]) tr[p][u]idx;ptr[p][u];cnt[p]tag;}
} int query(int p,int a,int b) {int ans0;for(int i18;i0;i--) {int uai1;if(!(bi1)) ptr[p][u];else {anscnt[tr[p][u]];ptr[p][!u];}if(!p) break;}return anscnt[p];
}void add(int x,int c,int val) {for(int ix;in;ilowbit(i)) insert(val,tree[i],c);
}int sum(int x,int a,int b) {int ans0;for(int ix;i;i-lowbit(i)) ansquery(tree[i],a,b);return ans;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]);int m; scanf(%d,m);for(int i1;im;i) {int l,r,a,b; scanf(%d%d%d%d,l,r,a,b);v[r].pb({l,i,a,b});}for(int i1;in;i) {if(pre[a[i]]) add(pre[a[i]],-1,a[i]);add(i,1,a[i]); pre[a[i]]i;for(auto x:v[i]) {ans[x.id]sum(i,x.a,x.b)-sum(x.l-1,x.a,x.b);}}for(int i1;im;i) printf(%d\n,ans[i]);return 0;
}
/**/
