祎隋

数对子
Description我们定义一个数对 (x,y) 是好的,当且仅当 x≤y,且 x xor y的二进制表示下有奇...
扫描右侧二维码阅读全文
15
2019/02

数对子

Description

我们定义一个数对 (x,y) 是好的,当且仅当 x≤y,且 x xor y的二进制表示下有奇数个 1

现在给定 nn 个区间 [li,ri],你需要对于每个 i∈[1,n],输出有几对好的数 (x,y)满足 x 和 y 都在 [l1,r1]∪[l2,r2]...∪[li,ri],即两个数都在前 i 个区间的并里

Input

第一行一个正整数 n

接下来 n 行每行两个整数 [li,ri],表示第 i个区间,保证 li≤ri

Ouput

输出 n 行,第 i行一个整数表示有几对好的数 (x,y) 满足 x,y 都在前 i 个区间的并里

Sample Input

3

1 7

3 10

9 20

Sample Output

12

25

100

Hint

对于 30%30% 的数据,有 1≤n≤1001≤n≤100,1≤li≤ri≤1001≤li≤ri≤100

对于 50%50% 的数据,有 1≤n≤10001≤n≤1000,1≤li≤ri≤232−11≤li≤ri≤232−1

对于 100%100% 的数据,有 1≤n≤1051≤n≤105, 1≤li≤ri≤232−11≤li≤ri≤232−1

时间限制:2s

空间限制:512MB

Solution

tips

先补充几个小知识点(快速求出一个数的二进制中有多少个1):

x=x&(x-1)(递归求法,适用于单个数)

表达式的意思就是:把x的二进制表示 从低位开始,将遇到的第一个为1的 二进制位 置0。

int calc=0;
while(x) x=x&(x-1),calc++;
calc即为所求值

求0到x中有多少二进制含1个数为奇数的:

long long calc(long long x)
{
    long long tmp=x,tot=0;
    while(tmp)
    {
        if(tmp&1)tot++;
        tmp>>=1;
    }
    return (x>>1)+((x&1) || (tot&1));
}
证明:00 01 10 11 100 101 110 111....继续下去可以发现规律是偶奇奇偶奇偶偶奇....
所以x>>1之前一半的,如果x为奇数(会少算一个)或其本身有奇数个1得加上

所以说探究性质a老哥(这个性质也可以记住)

p.s.当线段树叶子节点有n个时,应开总共2^(log2n+1)个点,即2*n个点

正经题解开始:

首先,对于每个数对(x,y), 若要x xor y的二进制表示下有奇数个 1,则必定一者含奇数个1,一者含偶数个。

证明:若两个都为奇数,1.则奇减奇等于偶(重叠个数为奇个)2.奇减偶先为奇(重叠个数为偶数个),奇加奇等于偶

​ 若两个都为偶数,则可同上证明

​ 一奇一偶,1.奇减奇等于偶,偶减奇等于奇,奇加偶等于奇2.奇减偶等于奇,偶减偶等于偶,偶加奇等于奇

所以我们采取线段树来维护区间含奇数个1和含偶数个1的个数,对于区间l,r,则用上述中所介绍的calc函数,来calc(r)-calc(l-1)得到奇数个1个数以及r-l+1-(calc(r)-calc(l-1))得到偶数个1个数

每次输入一个区间加进去统计一个区间,然后输出总的相乘即可。p.s.线段树很好的解决了区间相交的问题,在以及统计过的区间标记vis[now]=1;

上代码:

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
ll num[maxn<<4][2];
int lc[maxn<<4],rc[maxn<<4],rt=0,np=0;
int n;
bool vis[maxn<<4];
void upload(int now){
    num[now][0]=num[lc[now]][0]+num[rc[now]][0];
    num[now][1]=num[lc[now]][1]+num[rc[now]][1];
}
ll calc(ll x)
{
    ll t=x,tot=0;
    while(t)
    {
        if(t&1)tot++;
        t>>=1;
    }
    return (x>>1)+((x&1) || (tot&1));
}
void update(int &now,ll l,ll r,ll x,ll y){
    if(!now) now=++np;
    if(vis[now]) return;
    if(l>=x&&r<=y){
        num[now][1]=calc(r)-calc(l-1);
        num[now][0]=r-l+1-num[now][1];
        vis[now]=1;
        return;
    }
    ll m=(l+r)>>1;
    if(y<=m)update(lc[now],l,m,x,y);
    else if(x>m)update(rc[now],m+1,r,x,y);
    else{
        update(lc[now],l,m,x,y);
        update(rc[now],m+1,r,x,y);
    }
    
    upload(now);
}
void init(){
    scanf("%d",&n);
    ll L,R,mx=1ll<<32;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&L,&R);
        update(rt,1,mx,L,R);
        printf("%lld\n",num[1][0]*num[1][1]);
    }
}
int main(){
    init();    
    
    return 0;
}
Last modification:February 15th, 2019 at 09:27 pm

Leave a Comment