[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;
}

[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;
}

[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 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 2588]Count on a tree

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

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

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

代码:

继续阅读

[BZOJ 3524]Couriers

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

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

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

代码:

继续阅读

[POJ 2104]K-th Number

我擦终于A了这题了!

主席树坑点多……

最好不要写指针主席树,不然容易TLE……(自带常数?

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

代码:

继续阅读