【纪中集训2019.3.25】芬威克树-白红宇

【纪中集训2019.3.25】芬威克树

阅读量：7035 次

发布时间：2019-06-28

本文共 2069 字，大约阅读时间需要 6 分钟。

题目

描述

第一段代码正确第用$k$进制$BIT$维护了前缀和；

第二段代码由于写错了$line \ 4$，所以意义发生了改变；

维护第二段代码执行$ADD(x,v)$和$QUERY(x)$的答案；

范围

$1 \le n \le 10^9 , 1 \le q \le 2 \times 10^5 , 2 \le k \le 10^5 $ ;

题解

首先不管如何变化，这都是一个树形结构；

但是由于$n$较大，所以无法直接支持维护树链；

设$k = t \times 2 ^ p (t \% 2=1)$ ;

对于$v = x 2^y (x \% 2=1)$；
- 1.当$y \ge p$时，执行ADD时$v$的最低位是不会改变的，同时由于$x$在$t$的意义下有逆元，所以$v$至多有一个满足$y\ge p $的儿子，即这些节点形成了很多条链；
- 2.当$y<p$时，执行一次加最低位值会让$y++$,注意有可能最低位变化然后重新来过，但是最多有$log_k n$次，即这些点最多向上$log_k n \times p = log_{k} n log_2 k = log_2 n $ 次就会到1中的链上去;

可以暴力$HASH$维护$2$，离散后用$BIT$维护$1$ ;

只需要找到$1$中的链的叶子，注意在链上每次的进位是确定的，为对最低位的高一位进1；

链叶子满足$x$处于最低位，同时无法退位，所以形如:$ (2x+1) 2^p k^y , (y \ge 0 , 0 \le x \lt \frac{\frac{t}{2^p}-1}{2}) $即可;

可以$klog \ k$倍增方便地找到这些位置；

时间复杂度应该是：$k log_2 k + q (log_2 n + log_2 q +loq_2 k ) $ ; ？(似乎和出题人分析的有点不太一样。。。)

orz 租酥雨

#include
      
       #define pb push_back#define mk make_pair#define fi first#define se second#define ull unsigned long long #define il inline #define rg register using namespace std;const int N=200010,M=31;int n,m,k,MX,A,B,S,cnt,id;struct data{int op,x,y;}Q[N];int f[N][M],bin[M];pair
       
        v1[N];//map
        
         mp1;//,mp2;vector
         
          vec[N],val[N],v2[N];ull pw[100];il char gc(){  static char*p1,*p2,s[1000000];  if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);  return(p1==p2)?EOF:*p1++;}il int rd(){  int x=0;char c=gc();  while(c<'0'||c>'9')c=gc();  while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();  return x;}const int sz=123451;struct Hash{  int o,hd[sz],nt[N*M],v[N*M],w[N*M];  int& operator [](const int&x){      int y=x%sz;      for(rg int i=hd[y];i;i=nt[i]){          if(v[i]==x)return w[i];      }      nt[++o]=hd[y],hd[y]=o,v[o]=x,w[o]=0;      return w[o];  }}mp1,mp2;il void init(){  int iv2=A+1>>1;  for(rg int i=1;i
          
           >1][0];      while((f[i][0]&1)==0)f[i][0]>>=1;  }  for(rg int i=1;i
           
            >=B; while(x&&((x&1)==0))x>>=1; for(rg int i=0;i