郑州seo网站排名优化公司,淘宝关键词推广,家谱用网站做,重庆建网站 私单正题
题目链接:https://www.luogu.com.cn/problem/P7470 题目大意
给出nnn个二元组(a,b)(a,b)(a,b)。 qqq次询问给出(l,r,c,d)(l,r,c,d)(l,r,c,d)表示询问[l,r][l,r][l,r]中有多少二元组满足cxora≤min(b,d)c\ xor\ a\leq min(b,d)c xor a≤min(b,d)。 1≤n,q≤1051\leq n,q\…正题
题目链接:https://www.luogu.com.cn/problem/P7470 题目大意
给出nnn个二元组(a,b)(a,b)(a,b)。
qqq次询问给出(l,r,c,d)(l,r,c,d)(l,r,c,d)表示询问[l,r][l,r][l,r]中有多少二元组满足cxora≤min(b,d)c\ xor\ a\leq min(b,d)c xor a≤min(b,d)。
1≤n,q≤1051\leq n,q\leq 10^51≤n,q≤105 解题思路
这个minminmin一看就很迷显然是让我们分两种情况讨论。
再把询问拆一下就变成了两个条件pos≤r/poslpos\leq r/poslpos≤r/posl且b≤d/bdb\leq d/bdb≤d/bd。
两个偏序条件的话直接上CDQCDQCDQ然后考虑两种情况怎么处理。
cxora≤bc\ xor\ a\leq bc xor a≤b这样对于每个二元组合法的ccc开业被拆成TrieTrieTrie上最多logloglog个区间建TrieTrieTrie即可cxora≤dc\ xor\ a\leq dc xor a≤d对于每组询问在TrieTrieTrie上跑区间求和即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N1e510,MN*24;
struct node{int w,l,id;
}q[N1],a[N];
int n,m,tot,rt1,rt2,ans[N];
vectornode v[N];
struct Trie1{int cnt,ch[M][2],w[M]; void Clear(){rt10;cnt0;return;}int Newp(){cnt;ch[cnt][0]ch[cnt][1]w[cnt]0;return cnt;}void Insert(int x,int d,int l,int val){if(!x)xNewp();if(d0){w[x];return;}int c(vald)1;if((ld)1){Insert(ch[x][c^1],d-1,l,val);if(!ch[x][c])ch[x][c]Newp();w[ch[x][c]]; }else Insert(ch[x][c],d-1,l,val);}int Ask(int x,int d,int val){if(!x)return 0;if(d0)return w[x];int c(vald)1;return Ask(ch[x][c],d-1,val)w[x];}
}T1;
struct Trie2{int cnt,ch[M][2],w[M];void Clear(){rt20;cnt0;return;}int Newp(){cnt;ch[cnt][0]ch[cnt][1]w[cnt]0;return cnt;}void Insert(int x,int d,int val){if(!x)xNewp();if(d0){w[x];return;}int c(vald)1;Insert(ch[x][c],d-1,val);w[x]w[ch[x][0]]w[ch[x][1]];return;}int Ask(int x,int d,int l,int val){if(d0)return w[x];int c(vald)1;if((ld)1)return Ask(ch[x][c^1],d-1,l,val)w[ch[x][c]];return Ask(ch[x][c],d-1,l,val);}
}T2;
bool cmp(node x,node y)
{return x.ly.l;}
void CDQ(int l,int r){if(lr)return;int mid(lr)1;CDQ(l,mid);CDQ(mid1,r);sort(al,amid1,cmp);T1.Clear();T2.Clear();tot0;for(int imid1;ir;i)for(int j0;jv[i].size();j)q[tot]v[i][j];sort(q1,q1tot,cmp);for(int i1,zl;itot;i){while(zmida[z].lq[i].l)T1.Insert(rt1,23,a[z].l,a[z].w),z;if(q[i].id0)ans[-q[i].id]-T1.Ask(rt1,23,q[i].w);else ans[q[i].id]T1.Ask(rt1,23,q[i].w);}for(int itot,zmid;i1;i--){while(zla[z].lq[i].l)T2.Insert(rt2,23,a[z].w),z--;if(q[i].id0)ans[-q[i].id]-T2.Ask(rt2,23,q[i].l,q[i].w);else ans[q[i].id]T2.Ask(rt2,23,q[i].l,q[i].w);}return;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d%d,a[i].w,a[i].l);for(int i1;im;i){int l,r,c,d;scanf(%d%d%d%d,l,r,c,d);v[l].push_back((node){c,d,-i});v[r1].push_back((node){c,d,i});}sort(q1,q1n,cmp);CDQ(1,n1);for(int i1;im;i)printf(%d\n,ans[i]);return 0;
}
