danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29170

[BZOJ 2653]middle

2017年1月31日 10:16 | Comments(0) | Category:题解 | Tags:

前几天想用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

2016年8月25日 12:27 | Comments(0) | Category:题解 | Tags:

某傻逼的卡评记录

终于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

2016年4月10日 13:15 | Comments(0) | Category:题解 | Tags:

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

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

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

代码:

[BZOJ 3524]Couriers

2016年2月12日 13:02 | Comments(0) | Category:题解 | Tags:

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

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

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

代码:

[POJ 2104]K-th Number

2016年2月11日 10:42 | Comments(0) | Category:题解 | Tags:

我擦终于A了这题了!

主席树坑点多……

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

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

代码: