latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年1月25日 星期一

[ codeforces ] Round #340 (Div. 2) E. XOR and Favorite Number

題目:
http://codeforces.com/contest/617/problem/E
給一個序列a1,a2,a3......an,再給一個k
接下來有m個詢問,給兩個數字l,r,問:
對於所有的i,j滿足l<=i<=j<=r,ai 到 aj所有數字的xor值=k的(i,j)有幾個

解法:
很直接就想到莫隊,關於該算法的實作就不多說了
先把序列做前綴xor再進行處理
注意計數用的陣列大小必須大於2^20 (1000000的二進位是11110100001001000000,但是兩個<1000000的數xor起來可以到11111111111111111111=(2^20)-1)
還有add,sub裡面操作的順序也要注意

code:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define MAXQ 100000
struct Q{
    int l,r,i,block;
    inline bool operator<(const Q &b)const{
        return block==b.block?r<b.r:block<b.block;
    }
}q[MAXQ+5];
int n,m,k;
int s[MAXN+5];
long long ans[MAXQ+5];
int p[(1<<20)+1];
long long cur_ans;
inline void add(int x){
    cur_ans+=p[x^k];
    ++p[x];
}
inline void sub(int x){
    --p[x];
    cur_ans-=p[x^k];
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        scanf("%d",&s[i]);
        s[i]^=s[i-1];
    }
    int lim=1+(int)sqrt(n);
    for(int i=0;i<m;++i){
        scanf("%d%d",&q[i].l,&q[i].r);
        --q[i].l;
        q[i].block=q[i].l/lim;
        q[i].i=i;
    }
    sort(q,q+m);
    for(int i=0,L=0,R=-1;i<m;++i){
        while(R<q[i].r)add(s[++R]);
        while(L>q[i].l)add(s[--L]);
        while(R>q[i].r)sub(s[R--]);
        while(L<q[i].l)sub(s[L++]);
        ans[q[i].i]=cur_ans;
    }
    for(int i=0;i<m;++i)printf("%lld\n",ans[i]);
    return 0;
}

沒有留言:

張貼留言