HDU 4867 Xor

Given n non-negative integers 

, We define a statistical function as follows: 

It will be noted that the nature of F(k) is calculated with the number of choices, such that: 

1)0≤b 

i≤a 

i，0≤i≤n-1，b 

i is a integer. 

2)b 

0 xor b 

1 xor ... xor b 

n-1 = k，xor means exclusive-or operation.   

Now given A and m operations, there are two different operations: 

1)C x y: set the value of ax to y； 

 2)Q x: calculate F(x) mod P, where P = 1000000007.

Input

The first line has a number T (T ≤ 10), indicating the number of test cases. 

For each test case, the first line contains tow integers n, m, (1≤n, m≤20000), denote the n, m that appear in the above description. Then next line contains n non-negative integers denote 

(0≤a  i≤1000). 

Then next m lines. Each line is one of the follow two: 

1)C x y: set the value of a  x to y；(0≤x≤n-1，0≤y≤1000) 

2)Q x: calculate F(x) mod P, where P = 1000000007. 

 The number of the first operation is not more than 5000. Output

For each Q operation, output the value of F(x) mod P.

Sample Input

12 5

3 2

Q 3

C 0 2

Q 3

Q 0

C 0 3

Sample Output

32

3

修改和询问的操作，显然可以联想到线段树，问题是如何处理复杂的数据。

考虑到结果肯定很大，并且ai很小，用状态压缩的思想，先把ai转成2进制，

像数位dp一样，把ai差分成不同的长度的前缀01串，以可能出现的最大数字1023

为例，可以被拆成：

1111111111

1111111110

111111110X

11111110XX

1111110XXX

...

0XXXXXXXXX

X代表了01任选，显然，每个数字被拆分成的状态数等于其二进制1的个数。

于是把状态和数量插入线段树中，合并的时候采用暴力的双循环，再排个序判断重复即可。

#include<map>
#include<ctime>
#include<cmath>    
#include<queue> 
#include<string>
#include<vector>
#include<cstdio>    
#include<cstring>  
#include<iostream>
#include<algorithm>    
#include<functional>
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))    
#define rep(i,j,k) for(int i=j;i<=k;i++)    
#define per(i,j,k) for(int i=j;i>=k;i--)    
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])    
#define inone(x) scanf("%d",&x)    
#define intwo(x,y) scanf("%d%d",&x,&y)    
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)  
#define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p) 
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define mp(i,j) make_pair(i,j)
#define ft first
#define sd second
typedef long long LL;
typedef pair<int, int> pii;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const int M = 5e6;
const double eps = 1e-10;
int T, n, m, a[N], x, y;
vector<pair<pii, int>> f[N], g;
char s[N];

void get(int x, int y)
{
  f[x].clear();
  f[x].push_back(mp(mp(y, 10), 1));
  for (int i = y; i; i -= low(i))
  {
    f[x].push_back(mp(mp(i - low(i), 10 - log(low(i)) / log(2)), low(i)));
  }
}

bool cmp(pair<pii, int>a, pair<pii, int>b)
{
  return a.ft < b.ft;
}

void merge(int x, int l, int r)
{
  f[x].clear(); g.clear();
  for (auto i : f[l]) for (auto j : f[r])
  {
    int k = i.ft.ft^j.ft.ft, L = min(i.ft.sd, j.ft.sd);
    k = (k >> (10 - L)) << (10 - L);
    g.push_back(mp(mp(k, L), 1LL * i.sd*j.sd%mod));
  }
  sort(g.begin(), g.end(), cmp);
  for (int i = 0, j; i < g.size(); i = j)
  {
    pair<pii, int> q = mp(g[i].ft, 0);
    for (j = i; j < g.size() && g[i].ft == g[j].ft; j++)
    {
      (q.sd += g[j].sd) %= mod;
    }
    f[x].push_back(q);
  }
}

void build(int x, int l, int r)
{
  if (l == r) { get(x, a[r]); return; }
  int mid = l + r >> 1;
  build(lson); build(rson);
  merge(x, x << 1, x << 1 | 1);
}

void change(int x, int l, int r, int u)
{
  if (l == r) { get(x, a[r]); return; }
  int mid = l + r >> 1;
  if (u <= mid) change(lson, u); else change(rson, u);
  merge(x, x << 1, x << 1 | 1);
}

int inv(int x) { return x == 1 ? 1 : 1LL * inv(mod%x)*(mod - mod / x) % mod; }

int main()
{
  for (inone(T); T; T--)
  {
    intwo(n, m);
    rep(i, 1, n) inone(a[i]);
    build(1, 1, n);
    while (m--)
    {
      scanf("%s", s);
      if (s[0] == 'C')
      {
        inone(x); ++x;
        inone(a[x]);
        change(1, 1, n, x);
      }
      else
      {
        inone(x);
        int ans = 0;
        for (auto i : f[1])
        {
          if ((i.ft.ft^x) >> (10 - i.ft.sd)) continue;
          (ans += 1LL * i.sd * inv(1 << (10 - i.ft.sd)) % mod) %= mod;
        }
        printf("%d\n", ans);
      }
    }
  }
  return 0;
}