本文主要是介绍[LOJ 5516]无聊的数对，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
无聊的数对
题解
好水的题呀，为什么还是这句话？？？
额，首先，我们知道要使得的__builtin_parityll(即它在二进制下1的个数是否为奇，一下简称parityll为奇的话，a与b的parityll一定是不同的。
这，还是证一下吧。
我们设有
个1，
有
个1，它们共有的1的个数为
，那么它们异或后的1的个数为
，它的奇偶性与
是相同的，所以要使得
的1个数为奇，
必定为奇，于是
与
的奇偶性不同。
于是答案就成了所有区间内偶数个1的个数乘上奇数个1的个数的积。
然后，我们发现数据规模为，明显不能直接用暴力。我们就想到了线段树维护所有已选的区间，加上一个动态开点就可以维护整个序列的值了。
时间复杂度是，还是不忽略32了。
源码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<bitset>
#include<set>
using namespace std;
#define MAXN 1000005
typedef long long LL;
#define int LL
typedef pair<int,int> pii;
#define gc() getchar()
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
int n,root,tot;
int lson[MAXN],rson[MAXN];
int tag[MAXN],odd[MAXN],even[MAXN];
int cal(int x){if(x&1LL)return x+1LL>>1LL;return (x>>1LL)+__builtin_parityll(x);
}
int calc(int l,int r){return cal(r)-cal(l-1);}
void insert(int &rt,int l,int r,int al,int ar){//printf("%d %d:%d %d\n",l,r,al,ar);if(!rt)rt=++tot;if(tag[rt])return ;if(al<=l&&r<=ar){rt=++tot;tag[rt]=1;odd[rt]=calc(l,r);even[rt]=r-l+1-odd[rt];//printf("%d %d:%d %d\n",l,r,odd[rt],even[rt]);return ;}int mid=l+r>>1LL;if(al<=mid)insert(lson[rt],l,mid,al,ar);if(ar>mid)insert(rson[rt],mid+1,r,al,ar);odd[rt]=odd[lson[rt]]+odd[rson[rt]];even[rt]=even[lson[rt]]+even[rson[rt]];tag[rt]|=tag[lson[rt]]&tag[rson[rt]];//printf("%d %d %d %d:%d %d\n",rt,tag[rt],l,r,odd[rt],even[rt]);
}
signed main(){read(n);for(int i=1;i<=n;i++){int l,r;read(l);read(r);insert(root,1,(1LL<<32LL),l,r);printf("%lld\n",odd[root]*even[root]);}return 0;
}
/*
*/
谢谢！！！
这篇关于[LOJ 5516]无聊的数对的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
