[BZOJ 5358][Lydsy1805月赛]口算训练

后几页有我会做的题……很好，我很安详，，，

考虑将所有数质因数分解。那么询问\([l, r]\)中所有数的积是否是\(d\)的倍数的本质就是对于\(d\)的每一类质因子，询问区间中该类质因子的指数之和是否不小于\(d\)中的。

考虑到数的范围都很小（不超过100000），我们可以先线性筛预处理，这样一次分解质因数的复杂度就降为了\(O(\log n)\)。至于维护区间每类质因子的指数和这种事……就用主席树处理吧。

代码：

/**************************************************************
    Problem: 5358
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2804 ms
    Memory:68408 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
const int maxn = 100005;
int minp[maxn], mint[maxn], minh[maxn];
int prm[maxn], pcnt;
bool vis[maxn];
void sieve() {
  const int N = 100000;
  vis[1] = true; pcnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      prm[++ pcnt] = i;
      minp[i] = pcnt; mint[i] = 1;
      minh[i] = i;
    }
    for(int j = 1; j <= pcnt && i * prm[j] <= N; j ++) {
      int v = i * prm[j];
      vis[v] = true; minp[v] = j;
      if(i % prm[j] == 0) {
        mint[v] = mint[i] + 1; minh[v] = minh[i] * prm[j];
        break;
      } else {
        mint[v] = 1; minh[v] = prm[j];
      }
    }
  }
}
 
const int bufsiz = 64 * 1024 * 1024;
char buf[bufsiz]; char *cur;
void init_buf() {
  cur = buf;
}
void *alloc(size_t size) {
  if(cur + size - buf > bufsiz) {
    return malloc(size);
  } else {
    char *ret = cur; cur += size;
    return ret;
  }
}
 
struct Node {
  int v; Node *lc, *rc;
};
Node *build_tree(int L, int R) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> v = 0; 
  if(L == R) {
    ret -> lc = ret -> rc = NULL;
  } else {
    int M = (L + R) / 2;
    ret -> lc = build_tree(L, M);
    ret -> rc = build_tree(M + 1, R);
  }
  return ret;
}
Node *add_p(Node *o, int L, int R, int p, int v) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> v = o -> v;
  ret -> lc = o -> lc; ret -> rc = o -> rc;
  if(L == R) {
    ret -> v += v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      ret -> lc = add_p(ret -> lc, L, M, p, v);
    } else {
      ret -> rc = add_p(ret -> rc, M + 1, R, p, v);
    }
  }
  return ret;
}
int query(Node *o, int L, int R, int p) {
  if(L == R) {
    return o -> v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      return query(o -> lc, L, M, p);
    } else {
      return query(o -> rc, M + 1, R, p);
    }
  }
}
 
Node *rt[maxn];
void solve() {
  init_buf();
  int n, m; scanf("%d%d", &n, &m);
  rt[0] = build_tree(1, pcnt);
  for(int i = 1; i <= n; i ++) {
    rt[i] = rt[i - 1];
    int x; scanf("%d", &x);
    while(x > 1) {
      int p = minp[x], t = mint[x];
      rt[i] = add_p(rt[i], 1, pcnt, p, t);
      x /= minh[x];
    }
  }
  while(m --) {
    int l, r, d; scanf("%d%d%d", &l, &r, &d);
    bool ok = true;
    while(d > 1) {
      int p = minp[d], t = mint[d];
      int st = query(rt[r], 1, pcnt, p) - query(rt[l - 1], 1, pcnt, p);
      if(st < t) {
        ok = false; break;
      }
      d /= minh[d];
    }
    if(ok) {
      puts("Yes");
    } else {
      puts("No");
    }
  }
}
 
int main() {
  sieve();
  int T; scanf("%d", &T);
  while(T --) {
    solve();
  }
  return 0;
}

题解 BZOJ 主席树 Comments(0) 2018年5月30日 13:24

[LibreOJ 2174][FJOI2016]神秘数 & [CC]FRBSUM

震惊！省选惊现CodeChef原题……竟然是为了……出原题难道不是普遍现象吗

这个题的思想肥肠喵啊（我膜了很长时间题解才看懂）……我争取给各位读者讲懂。

首先对于最后的答案\(x + 1\)，一定说明\([1, x]\)都会被凑出来。那么我们可以考虑去维护这个前缀区间。

考虑把数从小到大加入。假设当前我们的可凑出来的前缀区间是\([1, r]\)，那么加入一个数\(x\)，如果说\(x > r + 1\)，那么把之前所有可能的子集和都加上这个\(x\)，一定凑不出来\(r + 1\)。并且这之后加入的数会越来越大，那个\(r\)不会再变大了，所以那个\(r\)就是答案了。

如果说\(x\leq r + 1\)呢？那么把前缀区间的每个数加上\(x\)都是可凑成数。所以前缀区间会变成\([1, r + x]\)。

然后观察出来这种性质之后，我们发现我们要考虑区间中不同的数，可以考虑主席树。我们建立一排主席树，对于查询\([L, R]\)，不妨假设当前的前缀区间是\([1, r]\)，然后考虑将其扩大。首先再加上大于\(r + 1\)的数是对扩大\(r\)没有意义的，所以我们就考虑在\([L, R]\)中找到所有权值处于\([1, r + 1]\)的数字的和（主席树可以派上用场），这样就是一个新的答案了。如果发现转移过去之后答案没有变大，那么以后也不会变大了，跳出来即可。

考虑分析一波复杂度。对于每一个\(r\)，转移到更大的\(r\)会让他至少加上\(r + 1\)，所以转移的次数是\(\log_2 s\)（这里假设\(s\)是所有数的和），然后每次一次转移的复杂度是\(\log_2 n\)，所以单次查询复杂度可以大致认为是\(\log^2 n\)。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 100005;
const int maxsiz = maxn * 40;
ll sumv[maxsiz]; int tot = 0;
int lc[maxsiz], rc[maxsiz];
int build_tree(int L, int R) {
  int ret = ++ tot;
  if(L < R) {
    int M = (L + R) / 2;
    lc[ret] = build_tree(L, M);
    rc[ret] = build_tree(M + 1, R);
  }
  return ret;
}
int update(int o, int L, int R, int p, int v) {
  int ret = ++ tot;
  sumv[ret] = sumv[o] + (ll(v));
  lc[ret] = lc[o], rc[ret] = rc[o];
  if(L < R) {
    int M = (L + R) / 2;
    if(p <= M) {
      lc[ret] = update(lc[ret], L, M, p, v);
    } else {
      rc[ret] = update(rc[ret], M + 1, R, p, v);
    }
  }
  return ret;
}
ll query(int o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return sumv[o];
  } else {
    int M = (L + R) / 2;
    ll ans = 0;
    if(ql <= M) ans += query(lc[o], L, M, ql, qr);
    if(qr > M) ans += query(rc[o], M + 1, R, ql, qr);
    return ans;
  }
}

int n;
ll A[maxn], A2[maxn];
int cnt;
void discretiz() {
  std::sort(A2 + 1, A2 + n + 1);
  cnt = std::unique(A2 + 1, A2 + 1 + n) - A2 - 1;
}
int get_p(ll v) {
  int ret = (std::lower_bound(A2 + 1, A2 + 1 + cnt, v) - A2);
  if(A2[ret] > v) ret --;
  return ret;
}

int T[maxn];
void init_tree() {
  T[0] = build_tree(1, cnt);
  for(int i = 1; i <= n; i ++) {
    T[i] = update(T[i - 1], 1, cnt, get_p(A[i]), A[i]);
  }
}
const ll INF = 1000000000LL;
ll calc_sum(int l, int r, int typ) {
  if(typ == 0) return 0LL;
  return query(T[r], 1, cnt, 1, typ) - query(T[l - 1], 1, cnt, 1, typ);
}
ll calc(int l, int r) {
  ll maxv = 0LL, R = 1LL;
  maxv = calc_sum(l, r, get_p(R));
  while(maxv >= R && R < INF) {
    R = std::min(maxv + 1LL, INF);
    maxv = calc_sum(l, r, get_p(R));
  }
  return maxv + 1LL;
}
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &A[i]); A2[i] = A[i];
  }
  discretiz(); init_tree();
  int q; scanf("%d", &q);
  while(q --) {
    int l, r; scanf("%d%d", &l, &r);
    printf("%lld\n", calc(l, r));
  }
  return 0;
}

题解 loj CodeChef FJOI 主席树 Comments(1) 2018年3月12日 08:58

[BZOJ 2653]middle

前几天想用Github+org-mode替代这个博客，后来想了想，还是算了吧。毕竟博客对大家更方便。

这个题真不愧是陈老师的题啊……exciting！

首先我们看到左端点在[tex][a,b][/tex]，右端点在[tex][c,d][/tex]，一股GSS5的气味扑来？

为了方便，我们先将序列离散化。然后我们将序列中大于等于x的值变为1，小于x的值变为-1，则某段区间的区间和若大于等于0，则该区间的中位数大于等于x，反之则其中位数小于x（注意，此题的中位数定义比较奇怪）。

然后我们可以对每个x建一棵树，然后二分答案，对于每个答案在对应的树上跑一遍GSS5即可（不过这题[tex]a<b<c<d[/tex]，所以不需要复杂的分类讨论）。

但是如果每个x都建一棵树，肯定会MLE吧？这个时候就要用主席树了= =

代码：

/**************************************************************
    Problem: 2653
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2220 ms
    Memory:1956 kb
****************************************************************/
 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=20005;
struct Node{
  Node *lc,*rc;
  int maxPSum,maxSSum,sum;
  Node(int x){
    lc=rc=NULL;
    maxPSum=maxSSum=sum=x;
  }
  Node(Node *l,Node *r){
    lc=l;rc=r;
  }
  void maintain(){
    maxPSum=max(lc->maxPSum,lc->sum+rc->maxPSum);
    maxSSum=max(rc->maxSSum,rc->sum+lc->maxSSum);
    sum=lc->sum+rc->sum;
  }
};
Node* build_tree(int L,int R){
  if(L==R){
    return new Node(1);
  }
  int M=L+(R-L)/2;
  Node *ans=new Node(build_tree(L,M),build_tree(M+1,R));
  ans->maintain();
  return ans;
}
int p,v;
Node* insert(Node *o,int L,int R){
  if(L==R){
    return new Node(v);
  }else{
    Node *ans=new Node(o->lc,o->rc);
    int M=L+(R-L)/2;
    if(p<=M){
      ans->lc=insert(ans->lc,L,M);
    }else{
      ans->rc=insert(ans->rc,M+1,R);
    }
    ans->maintain();
    return ans;
  }
}
int ql,qr;
Node queryPSum(Node *o,int L,int R){
  if(ql<=L && R<=qr){
    return *o;
  }else{
    int M=L+(R-L)/2;
    if(qr<=M){
      return queryPSum(o->lc,L,M);
    }else{
      if(ql<=M){
        Node l=queryPSum(o->lc,L,M);
        Node r=queryPSum(o->rc,M+1,R);
        Node ans(l.sum+r.sum);
        ans.maxPSum=max(l.maxPSum,l.sum+r.maxPSum);
        return ans;
      }else{
        return queryPSum(o->rc,M+1,R);
      }
    }
  }
}
Node querySSum(Node *o,int L,int R){
  if(ql<=L && R<=qr){
    return *o;
  }else{
    int M=L+(R-L)/2;
    if(qr<=M){
      return querySSum(o->lc,L,M);
    }else{
      if(ql<=M){
        Node l=querySSum(o->lc,L,M);
        Node r=querySSum(o->rc,M+1,R);
        Node ans(l.sum+r.sum);
        ans.maxSSum=max(r.maxSSum,r.sum+l.maxSSum);
        return ans;
      }else{
        return querySSum(o->rc,M+1,R);
      }
    }
  }
}
int querySum(Node *o,int L,int R){
  if(ql<=L && R<=qr){
    return o->sum;
  }else{
    int M=L+(R-L)/2;
    int ans=0;
    if(ql<=M){
      ans+=querySum(o->lc,L,M);
    }
    if(qr>M){
      ans+=querySum(o->rc,M+1,R);
    }
    return ans;
  }
}
Node *root[maxn];
 
int n;
int A[maxn],A2[maxn];
vector<int> V[maxn];
int lsh_siz;
inline void lsh(){
  sort(A2+1,A2+1+n);
  lsh_siz=unique(A2+1,A2+1+n)-A2-1;
  for(register int i=1;i<=n;i++){
    A[i]=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
    V[A[i]].push_back(i);
  }
}
int q[4];
inline bool Check(int M){
  register int l,m,r;
  if(q[1]+1<=q[2]-1){
    ql=q[1]+1;
    qr=q[2]-1;
    m=querySum(root[M],1,lsh_siz);
  }else{
    m=0;
  }
  ql=q[0];qr=q[1];
  l=querySSum(root[M],1,lsh_siz).maxSSum;
  ql=q[2];qr=q[3];
  r=queryPSum(root[M],1,lsh_siz).maxPSum;
#ifdef DEBUG
  printf("Case %d: %d %d %d\n",M,l,m,r);
#endif
  return l+m+r>=0;
}
int main(){
  register int i,j,L,M,R,ans=0;
  int t;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
    A2[i]=A[i];
  }
  lsh();
  root[1]=build_tree(1,n);
  for(i=2;i<=lsh_siz;i++){
    root[i]=root[i-1];
    for(j=0;j<V[i-1].size();j++){
      p=V[i-1][j];
      v=-1;
      root[i]=insert(root[i],1,lsh_siz);
    }
  }
  scanf("%d",&t);
  while(t--){
    for(i=0;i<4;i++){
      scanf("%d",&q[i]);
      q[i]=(q[i]+ans)%n;
    }
    sort(q,q+4);
    for(i=0;i<4;i++){
      q[i]++;
      #ifdef DEBUG
      printf("%d ",q[i]);
      if(i==3){
        puts("");
      }
      #endif
    }
    L=1;R=lsh_siz;
    while(true){
      if(R-L<=3){
        for(i=R;i>=L;i--){
          if(Check(i)){
            ans=A2[i];
            break;
          }
        }
        break;
      }
      M=L+(R-L)/2;
      if(Check(M)){
        L=M;
      }else{
        R=M;
      }
    }
    printf("%d\n",ans);
  }
  return 0;
}

题解 BZOJ 二分答案 主席树 Comments(0) 2017年1月31日 10:16

[BZOJ 1901]Dynamic Rankings

某傻逼的卡评记录

终于A了！

做了4个月了，终于A了！

这个题其实不难。只要用树状数组维护主席树即可。不过请注意，此题的实际数据范围远比10000大！

代码：

/**************************************************************
    Problem: 1901
    User: danihao123
    Language: C++
    Result: Accepted
    Time:540 ms
    Memory:32712 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=120051;
const int maxlogn=31;
const int maxnode=maxn*20;
 
// ChairTree
int sumv[maxnode];
int lc[maxnode],rc[maxnode];
int ct_cnt=0;
int build_tree(int L,int R){
    int ans=++ct_cnt;
    if(R>L){
        int M=L+(R-L)/2;
        lc[ans]=build_tree(L,M);
        rc[ans]=build_tree(M+1,R);
    }
    return ans;
}
int p,v;
int update(int o,int L,int R){
    int ans=++ct_cnt;
    sumv[ans]=sumv[o];
    lc[ans]=lc[o];
    rc[ans]=rc[o];
    if(R>L){
        int M=L+(R-L)/2;
        if(p<=M)
            lc[ans]=update(lc[ans],L,M);
        else
            rc[ans]=update(rc[ans],M+1,R);
    }
    sumv[ans]+=v;
    return ans;
}
int LT_siz,RT_siz;
int LT[maxlogn],RT[maxlogn];
int query(int L,int R,int k){
    if(L==R)
        return L;
    int i;
    int LT_ans=0,RT_ans=0,the_ans,M=L+(R-L)/2;
    for(i=1;i<=LT_siz;i++)
        LT_ans+=sumv[lc[LT[i]]];
    for(i=1;i<=RT_siz;i++)
        RT_ans+=sumv[lc[RT[i]]];
    the_ans=RT_ans-LT_ans;
    if(k<=the_ans){
        for(i=1;i<=LT_siz;i++)
            LT[i]=lc[LT[i]];
        for(i=1;i<=RT_siz;i++)
            RT[i]=lc[RT[i]];
        return query(L,M,k);
    }else{
        for(i=1;i<=LT_siz;i++)
            LT[i]=rc[LT[i]];
        for(i=1;i<=RT_siz;i++)
            RT[i]=rc[RT[i]];
        return query(M+1,R,k-the_ans);
    }
}
 
int rt[maxn];
int siz;
inline int lowbit(int x){
    return x&(-x);
}
int n;
void change(int pos,int value,int delta){
    p=value;
    v=delta;
    while(pos<=n){
        rt[pos]=update(rt[pos],1,siz);
        pos+=lowbit(pos);
    }
}
int get_ans(int l,int r,int k){
    int temp=l-1;
    LT_siz=RT_siz=0;
    while(temp>0){
        LT[++LT_siz]=rt[temp];
        temp-=lowbit(temp);
    }
    while(r>0){
        RT[++RT_siz]=rt[r];
        r-=lowbit(r);
    }
    return query(1,siz,k);
}
int pre[maxn];
int A[maxn],A2[maxn];
int real_siz=0;
void init_CT(){
    register int i,pos;
    sort(A2+1,A2+1+real_siz);
    siz=unique(A2+1,A2+1+real_siz)-A2-1;
    rt[0]=build_tree(1,siz);
    for(i=1;i<=n;i++)
        rt[i]=rt[0];
    for(i=1;i<=n;i++){
        pos=lower_bound(A2+1,A2+1+siz,pre[i])-A2;
        change(i,pos,1);
    }
}
inline int get_lsh(int x){
    return lower_bound(A2+1,A2+1+siz,x)-A2;
}
 
int Query[maxn][4];
int main(){
    int m,u,v,d;
    char buf[3];
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&pre[i]);
        A2[++real_siz]=pre[i];
    }
    for(i=1;i<=m;i++){
        scanf("%s%d%d",buf,&u,&v);
        Query[i][1]=u;
        Query[i][2]=v;
        if(buf[0]=='C'){
            Query[i][0]=1;
            A2[++real_siz]=v;
        }else{
            Query[i][0]=0;
            scanf("%d",&Query[i][3]);
        }
    }
    init_CT();
    for(i=1;i<=m;i++){
        if(Query[i][0]){
            change(Query[i][1],get_lsh(pre[Query[i][1]]),-1);
            pre[Query[i][1]]=Query[i][2];
            change(Query[i][1],get_lsh(Query[i][2]),1);
        }else{
            printf("%d\n",A2[get_ans(Query[i][1],Query[i][2],Query[i][3])]);
        }
    }
    return 0;
}

题解 BZOJ ZJU 区间K大 主席树 树状数组 Comments(1) 2016年8月25日 12:27

[BZOJ 2588]Count on a tree

泥萌感觉我还能说什么……

这题就是DFS序套主席树，顺便带上倍增LCA，但有两大坑点：

  1. 存放数据不一定要用long long，但输入必须要。
  2. 输出数据蛋疼，最后一行行末没回车。

代码：

继续阅读

题解 SPOJ bzoj DFS序 主席树 倍增LCA Comments(0) 2016年4月10日 13:15

[BZOJ 3524]Couriers

这道题有了主席树，就是裸题了……

只要用主席树维护出现次数，然后二分求解即可

但是！数组一定要开大，开大，再开大，重要的事情说三遍！

代码：

继续阅读

题解 POI bzoj 主席树 二分 Comments(0) 2016年2月12日 13:02

[POJ 2104]K-th Number

我擦终于A了这题了！

主席树坑点多……

最好不要写指针主席树，不然容易TLE……（自带常数？）

并且注意，一定要把数组开大，开大，再开大，重要的事情说三遍

代码：

继续阅读

题解 POJ 区间K大 主席树 Comments(0) 2016年2月11日 10:42