社区讨论
d<b部分分求助,对拍过了几万组吧,洛谷过不了
P7470 [NOI Online 2021 提高组] 岛屿探险参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @locgyfnb
- 此快照首次捕获于
- 2023/10/30 13:38 2 年前
- 此快照最后确认于
- 2023/11/16 18:16 2 年前
CPP
#include<bits/stdc++.h>
#define Int int
#define db double
#define INF 1<<30
using namespace std;
const int p =1e5+5;
const int maxn = 25e5 + 3;
int a[p],b[p];
int Trie[maxn][2];
int rot[maxn];
int size[maxn];
int v = -1,pool = 0;
template<typename _T>
inline void read(_T &x)
{
x= 0 ;int f =1;char s=getchar();
while(s<'0' ||s>'9') {f =1;if(s == '-')f =- 1;s=getchar();}
while('0'<=s&&s<='9'){x = (x<<3) + (x<<1) + s - '0';s= getchar();}
x*=f;
}
inline void insert(int val) // a_i 建Trieæ ‘
{
int pre = rot[v];
int x = rot[++v] = ++pool;
for(int i=23;i>=0;i--)
{
int ch = (1<<i&val)?1:0;
size[pool] = size[pre] + 1;
Trie[pool][ch] = pool + 1;
Trie[pool][!ch] = Trie[pre][!ch];
pre = Trie[pre][ch];
++pool;
}
size[pool] = size[pre] + 1;
}
inline int query(int l,int r,int c,int d)
{
int Ans = 0;
int L = rot[l];
int R = rot[r];
for(int i=23;i>=0;i--)
{
int od = (1<<i&d)?1:0;
int cp = (1<<i&c)?1:0;
int ch;
if(od)
{
Ans += size[Trie[R][cp]] - size[Trie[L][cp]];
if(!Trie[R][!cp]) return Ans;
R = Trie[R][!cp];
L = Trie[L][!cp];
}
else
{
if(!Trie[R][cp]) return Ans;
R = Trie[R][cp];
L = Trie[L][cp];
}
}
Ans += size[R] - size[L];
return Ans;
}
signed main()
{
// freopen("In.in","r",stdin);
// freopen("my.out","w",stdout);
int n,m;
read(n);read(m);
for(int i=1;i<=n;i++)
{
read(a[i]);
read(b[i]);
}
insert(0);
for(int i=1;i<=n;i++)
{
insert(a[i]);
}
int Ans = 0;
for(int i=1,l,r,c,d;i<=m;i++)
{
read(l);
read(r);
read(c);
read(d);
printf("%d\n" , query(l - 1 , r , c , d));
}
// system("pause");
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...