Codeforces Round#340(Div.2)E.XOR and Favorite Number(ブロック(java))
4652 ワード
タイトル:
n個の長さのシーケンス、m個の問い合わせ、1個の問い合わせ[L,R]、求めて[L,R]またどれだけのサブ区間のxorとk
n, m and k (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000)
考え方:
元の配列の接頭辞と配列について,すなわち,[L,R]中の(l,r)Al^Ar=kの対の数を尋ねる.
だからブロックは解決しやすい
コード:
n個の長さのシーケンス、m個の問い合わせ、1個の問い合わせ[L,R]、求めて[L,R]またどれだけのサブ区間のxorとk
n, m and k (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000)
考え方:
元の配列の接頭辞と配列について,すなわち,[L,R]中の(l,r)Al^Ar=kの対の数を尋ねる.
だからブロックは解決しやすい
コード:
import java.util.*;
import java.math.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
Scanner in = new Scanner(inputStream);
PrintWriter out = new PrintWriter(outputStream);
TaskE solver = new TaskE();
solver.solve(1, in, out);
out.close();
}
static class MyComprator implements Comparator {
public int compare(Object arg0, Object arg1) {
node a = (node)arg0;
node b = (node)arg1;
if(a.id != b.id) return a.id - b.id;
return a.Y - b.Y;
}
}
static node []op;
static int []cnt = new int[3000000];
static int []a;
static int block = (int) Math.sqrt(100000);
static long []res;
static class TaskE {
public void solve(int testNumber, Scanner in, PrintWriter out) {
int n = in.nextInt();
int m = in.nextInt();
int K = in.nextInt();
a = new int[n + 1];
op = new node[m];
res = new long[m];
for(int i = 0; i < m; i ++) op[i] = new node(0, 0, 0);
for(int i = 1; i <= n; i ++) a[i] = in.nextInt();
for(int i = 0; i < m; i ++) {
op[i].X = in.nextInt();
op[i].X --;
op[i].Y = in.nextInt();
op[i].getID();
op[i].ID = i;
}
Arrays.sort(op, new MyComprator());
int curl = 0, curr = 0;
int L = 0, R = -1;
long ans = 0;
for(int i = 0; i < m; i ++) {
while(L < op[i].X) {
curl ^= a[L];
cnt[curl] --;
ans -= cnt[curl ^ K];
L ++;
}
while(L > op[i].X) {
L --;
ans += cnt[curl ^ K];
cnt[curl] ++;
curl ^= a[L];
}
while(R > op[i].Y) {
cnt[curr] --;
ans -= cnt[curr ^ K];
curr ^= a[R];
R --;
}
while(R < op[i].Y) {
R ++;
curr ^= a[R];
ans += cnt[curr ^ K];
cnt[curr] ++;
}
res[op[i].ID] = ans;
}
for(int i = 0; i < m; i ++) out.println(res[i]);
}
}
static class node {
int X, Y;
int id, ID;
node(int X, int Y, int Z) {
this.X = X;
this.Y = Y;
this.id = Z;
}
public void getID() {
this.id = X / block;
}
}
static class pii implements Comparable<pii> {
int X, Y;
pii(int X, int Y) {
this.X = X;
this.Y = Y;
}
public int compareTo(pii a) {
if(this.X - a.X != 0) return this.X - a.X;
else return this.Y - a.Y;
}
}
static class Scanner {
BufferedReader br;
StringTokenizer st;
public Scanner(InputStream in) {
br = new BufferedReader(new InputStreamReader(in));
eat("");
}
private void eat(String s) {
st = new StringTokenizer(s);
}
public String nextLine() {
try {
return br.readLine();
} catch (IOException e) {
return null;
}
}
public boolean hasNext() {
while (!st.hasMoreTokens()) {
String s = nextLine();
if (s == null)
return false;
eat(s);
}
return true;
}
public String next() {
hasNext();
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
public BigInteger nextBigInteger() {
return new BigInteger(next());
}
}
}