problem on trie

Revision en1, by Tornad0, 2016-07-28 22:04:31

Hi, today I learned Trie:D and I solved a easy problem. Here is my code on the problem

include

int const N = 1000002; int const BITS = 31;

int link[N * BITS][2]; int a[N], num[N * BITS];

int main() { int n, k; //read the cutest data:D scanf("%d%d", &n, &k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for (int i = 1; i <= n; i++) a[i] ^= a[i — 1]; int freak = 2; int root = 1; long long ans = 0; for (int i = 0; i <= n; i++) { int v = root; //get all that less than K :D for (int b = BITS — 1; b >= 0 && v > 0; b--) { int curAi = (a[i] >> b) & 1; int curK = (k >> b) & 1; if (curK == 1) { if (link[v][curAi] > 0) { ans += num[link[v][curAi]]; } } v = link[v][curAi ^ curK]; } v = root;

//insert a[i] to trie:D
for (int b = BITS - 1; b >= 0; b--) {
  num[v]++;
  int cur = (a[i] >> b) & 1;
  if (link[v][cur] == 0) {
    link[v][cur] = freak++;
  }
  v = link[v][cur];
}
num[v]++;

} //ans get those less than K:D printf("%I64d\n", (long long) n * (n + 1) / 2 — ans); }

That's all. **** I will be back:D

Tags trie, stupid:), i will be back

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Tornad0 2016-07-28 22:04:31 1251 Initial revision (published)