SnackDown 2017 Online Elimination Round Prefix XOR

题目传送门

题意

给出$n$个数,定义上升为$a_i\leq a_i \quad xor \quad a_{i+1} \leq a_i \quad xor \quad a_{i+1} \quad xor \quad a_{i+2} \leq \dots \leq a_i \quad xor \quad a_{i+1} \quad xor \quad \dots \quad xor \quad a_{j}$,问每个区间的上升数对有多少?

思路

设$rig_i$表示以$i$为区间左端,使$(i,j)$满足上升的最大$j$。 设$sum_i$表示$xor$前缀和。 如果$a_r \quad xor \quad a_{r-1} \quad xor \quad \dots \quad xor \quad a_{i-1}>
a_{r+1} \quad xor \quad a_{r} \quad xor \quad \dots \quad xor \quad a_{i-1} $则不满足条件,那么$rig_i\leq r$。 即: 如果$sum_r \quad xor \quad sum_{i-1}> sum_{r+1} \quad xor \quad sum_{i-1} $则不满足条件,那么$rig_i\leq r$。 由于$xor$是位运算,所以考虑二进制下优化。 要满足条件,必须使$sum_r$与$sum_{r+1}$中至少有一位在二进制下不相同。 假设不相同的最高位是第$k$位,那么$sum_{i−1}$的第$k$位其实就有了限制,易得: (二进制下)
  1. $sum_r$的第$k$位为0,那么$sum_{i-1}$的第$k$位必须是1。
  2. $sum_r$的第$k$位为1,那么$sum_{i-1}$的第$k$位必须是0。
那么我们可以倒序枚举$i$,记录$S[j][0/1]$表示当前第$j$位限制为$0/1$时的位置,那样就可以快速求出$rig_i$了。 如果$[l,r]$不存在$rig_i>r$,那么答案显然就是$rig_i-i+1(l \leq i \leq r $且$ rig_i \leq r)$,但如果存在$rig_i>r$,由于不能越界,该部分的答案应该就是$r-i+1(l \leq i \leq r $且$ rig_i > r)$。由于强制在线,用主席树就可以解决了。
#include<bits/stdc++.h>
#define int long long
#define MAXN 600010 
using namespace std;
int n,m,q,Qt;
int a[MAXN],b[MAXN],rt[MAXN],xo[MAXN],rig[MAXN],S[31][500],Q,ans,ntt;
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
struct node{
    int l,r,sum,cnt;
}tree[MAXN*20];
void insert(int &x,int y,int l,int r,int p){
    x=++ntt;
    tree[x]=tree[y];
    if(l==r){
        tree[x].sum+=p;
        tree[x].cnt++;
        return ;
    }
    int mid=(l+r)>>1;
    if(p<=mid) insert(tree[x].l,tree[y].l,l,mid,p);
    else insert(tree[x].r,tree[y].r,mid+1,r,p);
    tree[x].sum=tree[tree[x].l].sum+tree[tree[x].r].sum;
    tree[x].cnt=tree[tree[x].l].cnt+tree[tree[x].r].cnt;
}
int Sum(int x,int y,int l,int r,int L,int R){
    if(L>R) return 0;
    if(L<=l&&r<=R){
        return tree[x].sum-tree[y].sum;
    }
    int mid=(l+r)>>1,res=0;
    if(L<=mid) res+=Sum(tree[x].l,tree[y].l,l,mid,L,R);
    if(R>mid) res+=Sum(tree[x].r,tree[y].r,mid+1,r,L,R);
    return res;
}
int Cnt(int x,int y,int l,int r,int L,int R){
    if(L>R) return 0;
    if(l>r) return 0;
    if(L<=l&&r<=R){
        return tree[x].cnt-tree[y].cnt;
    }
    int tmp=tree[tree[y].l].cnt-tree[tree[x].l].cnt;
    int mid=(l+r)>>1,res=0;
    if(L<=mid) res+=Cnt(tree[x].l,tree[y].l,l,mid,L,R);
    if(R>mid) res+=Cnt(tree[x].r,tree[y].r,mid+1,r,L,R);
    return res;
}
int Ge(int x){
    ++x;
    return x*(x-1)/2;
}
signed main(){
    n=read();Qt=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) xo[i]=xo[i-1]^a[i];
    for(int i=0;i<=31;i++) S[i][0]=S[i][1]=n+1;
    for(int i=n;i>=1;i--){
        rig[i]=n+1;
        for(int j=0;j<=31;j++) rig[i]=min(rig[i],S[j][(xo[i-1]>>j)&1]);
        rig[i]--;
        for(int k=31;k>=0;k--)
            if(((xo[i-1]>>k)&1)^((xo[i]>>k)&1)){
                S[k][(xo[i]>>k)&1]=i;
                break;
            }
    }
    for(int i=1;i<=n;i++) insert(rt[i],rt[i-1],1,n,rig[i]);
    Q=read();
    while(Q--){
        int x,y,l,r;
        x=read();y=read();
        x=(x+ans*Qt)%n;y=(y+ans*Qt)%n;
        x++;y++;
        l=min(x,y);r=max(x,y);
        ans=Sum(rt[r],rt[l-1],1,n,l,r)+Cnt(rt[r],rt[l-1],1,n,r+1,n)*r-(Ge(r)-Ge(l-1))+(r-l+1);
        write(ans);putchar('\n');
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇