danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29165

[BZOJ 1176][Balkan2007]Mokia

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

CDQ分治第一题……同时也是CDQ分治模板提。

感觉CDQ分治思路好秒啊……似乎在分治过程中做了个归并排序……

代码:

/**************************************************************
    Problem: 1176
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4364 ms
    Memory:17228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxw=2000005;
const int maxq=10005;
const int maxn=160001+4*maxq;
int cnt=0;
struct Query{
  int ans_id;
  int x,y,d,v;
  Query(){}
  Query(int a,int b,int di,int ap){
    x=a;y=b;
    d=di;
    ans_id=ap;
  }
  Query(int a,int b,int value){
    x=a;y=b;
    v=value;
    d=0;
  }
  inline bool isQuery(){
    return d!=0;
  }
};
 
int w;
int T[maxw];
inline int lowbit(int x){
  return x&(-x);
}
inline void add(int p,int v){
  while(p<=w){
    T[p]+=v;
    p+=lowbit(p);
  }
}
inline int sum(int p){
  register int x=0;
  while(p>0){
    x+=T[p];
    p-=lowbit(p);
  }
  return x;
}
inline void clear(int p){
  while(p<=w && T[p]!=0){
    T[p]=0;
    p+=lowbit(p);
  }
}
 
Query Q[maxn],tmp[maxn];
int ans[maxn];
void CDQ(int L,int R){
  if(L==R){
    return;
  }
  int M=L+(R-L)/2;
  CDQ(L,M);
  CDQ(M+1,R);
  int p,p1,p2;
  for(p=1,p1=L,p2=M+1;p<=(R-L+1);p++){
    if((Q[p1].x<=Q[p2].x && p1<=M) || p2>R){
      tmp[p]=Q[p1];
      if(!Q[p1].isQuery()){
        add(Q[p1].y,Q[p1].v);
      }
      p1++;
    }else{
      tmp[p]=Q[p2];
      if(Q[p2].isQuery()){
        ans[Q[p2].ans_id]+=sum(Q[p2].y)*Q[p2].d;
      }
      p2++;
    }
  }
  for(p=1,p1=L;p<=(R-L+1);p++,p1++){
    if(!Q[p1].isQuery()){
      clear(Q[p1].y);
    }
    Q[p1]=tmp[p];
  }
}
 
int main(){
  int S,t,x,y,a,b;
  register int ans_cnt=0;
  scanf("%d%d",&S,&w);
  while(true){
    scanf("%d",&t);
    if(t==3){
      break;
    }
    scanf("%d%d%d",&x,&y,&a);
    // x++;y++;
    if(t==1){
      Q[++cnt]=Query(x,y,a);
    }else{
      scanf("%d",&b);
      // a++;b++;
      ans_cnt++;
      ans[ans_cnt]=(a-x+1)*(b-y+1)*S;
      Q[++cnt]=Query(a,b,1,ans_cnt);
      Q[++cnt]=Query(x-1,b,-1,ans_cnt);
      Q[++cnt]=Query(a,y-1,-1,ans_cnt);
      Q[++cnt]=Query(x-1,y-1,1,ans_cnt);
    }
  }
  CDQ(1,cnt);
  for(register int i=1;i<=ans_cnt;i++){
    printf("%d\n",ans[i]);
  }
  return 0;
}

[BZOJ 3155]Preprefix sum

2016年10月22日 20:37 | Comments(0) | Category:题解 | Tags:

蛮有意思的一题……

考虑询问[tex]SS_i[/tex],[tex][1,i][/tex]中的每个位置[tex]j[/tex]在答案中被计算的次数为[tex]i-j+1[/tex],然后式子就可以变成这样:

[tex]\Sigma_{j=1}^{i} A[j]*(i-j+1)[/tex]

[tex](i+1)*\Sigma_{j=1}^{i} A[j]-\Sigma_{j=1}^{i} A[j]*j[/tex]

这样问题就简单多了,开两个树状数组乱搞搞即可。

代码:

/**************************************************************
    Problem: 3155
    User: danihao123
    Language: C++
    Result: Accepted
    Time:464 ms
    Memory:3164 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
const int maxn=100005;
typedef long long ll;
int n;
ll A[maxn];
ll C_1[maxn]; // 正常的BIT
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int p,ll v){
    while(p<=n){
        C_1[p]+=v;
        p+=lowbit(p);
    }
}
inline ll sum(int p){
    register ll ans=0;
    while(p>0){
        ans+=C_1[p];
        p-=lowbit(p);
    }
    return ans;
}
ll C_2[maxn]; // 累积的BIT
inline void add_2(int p,ll v){
    register int pos=p;
    while(pos<=n){
        C_2[pos]+=((ll)p)*v;
        pos+=lowbit(pos);
    }
}
inline ll sum_2(int p){
    register ll ans=0;
    while(p>0){
        ans+=C_2[p];
        p-=lowbit(p);
    }
    return ans;
}
 
int main(){
    int m,p;
    ll v;
    register int i;
    char *buf=(char*)calloc(10,1);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
        add(i,A[i]);
        add_2(i,A[i]);
    }
    while(m--){
        scanf("%s%d",buf,&p);
        if(buf[0]=='Q'){
            printf("%lld\n",((ll)p+1LL)*sum(p)-sum_2(p));
        }else{
            scanf("%lld",&v);
            add(p,v-A[p]);
            add_2(p,v-A[p]);
            A[p]=v;
        }
    }
    free(buf);
    return 0;
}

[BZOJ 3333]排队计划

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

传说中的大结论题TAT

假设每个数的后面小于它的数的个数为[tex]f[i][/tex](其位置为[tex]i[/tex]),那么逆序对数显然为[tex]\Sigma f[i][/tex]。

每次操作,只需要将涉及到的数的[tex]f[i][/tex]清为0即可。

为什么呢?任何数的后面比他小的数肯定也被一起拉出来排序了,所以这些数的[tex]f[i][/tex]要被清零。其他数为什么不收这个影响呢?因为这之后的比他小的位置,有的可能没被操作,有的可能被操作了。但是就算被操作了,放到后面位置的数照样会比这个数小(因为这个数如果在第一个选定位置的后面(在前面更是不受影响)还没被操作,肯定比那个第一个位置数还大)。

还有一个细节,一个被操作过的数不需要再被操作一遍,操作完了直接设为INF即可。

代码:

/**************************************************************
    Problem: 3333
    User: danihao123
    Language: C++
    Result: Accepted
    Time:7920 ms
    Memory:24264 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <utility>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=500005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
int A[maxn];
pii minv[maxnode];
inline void maintain(int o){
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(int o,int L,int R){
    if(L==R){
        minv[o]=make_pair(A[L],L);
    }else{
        int M=L+(R-L)/2;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
        maintain(o);
    }
}
int ql,qr;
pii query_min(int o,int L,int R){
    if(ql<=L && R<=qr){
        return minv[o];
    }else{
        int M=L+(R-L)/2;
        pii ans=make_pair(INF,INF);
        if(ql<=M)
            ans=min(ans,query_min(o<<1,L,M));
        if(qr>M)
            ans=min(ans,query_min(o<<1|1,M+1,R));
        return ans;
    }
}
int p;
void update(int o,int L,int R){
    if(L==R){
        minv[o].first=INF;
    }else{
        int M=L+(R-L)/2;
        if(p<=M)
            update(o<<1,L,M);
        else
            update(o<<1|1,M+1,R);
        maintain(o);
    }
}
 
int lsh_siz;
int C[maxn];
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int p){
    while(p<=lsh_siz){
        C[p]++;
        p+=lowbit(p);
    }
}
inline int sum(int p){
    int ans=0;
    while(p>0){
        ans+=C[p];
        p-=lowbit(p);
    }
    return ans;
}
 
inline int readint(){
    register int x;
    register char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[21];
template<typename T>
inline void putint(T x){
    register int i,p=0;
    if(!x){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(bf[i]+'0');
    putchar('\n');
}
int n;
int A2[maxn],f[maxn];
int main(){
    register int i,m,pos;
    register ull ans=0;
    pii temp;
    n=readint();
    m=readint();
    for(i=1;i<=n;i++){
        A[i]=readint();
        A2[i]=A[i];
    }
    sort(A2+1,A2+1+n);
    lsh_siz=unique(A2+1,A2+1+n)-A2-1;
    for(i=n;i>=1;i--){
        pos=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
        f[i]=sum(pos-1);
        ans+=f[i];
        add(pos);
    }
    putint(ans);
    build_tree(1,1,n);
    while(m--){
        pos=readint();
        ql=pos;
        qr=n;
        while(true){
            temp=query_min(1,1,n);
            if(temp.first>A[pos])
                break;
            p=temp.second;
            ans-=f[p];
            f[p]=0;
            update(1,1,n);
        }
        putint(ans);
    }
    return 0;
}

[POJ 2352]Stars

2016年9月19日 12:17 | Comments(0) | Category:题解 | Tags:

刚开始竟然还以为是强制离散化的二维Fenwick树……噫……注意读题。

这个题的坐标是按Y升序给出(Y相同则按X升序),所以说直接Fenwick树搞搞即可……

代码:

#include <cstdio>
const int maxn=15005,maxX=32010;
int C[maxX];
inline int lowbit(int x){
	return x&(-x);
}
inline void Add(int pos,int v){
	while(pos<=maxX){
		C[pos]+=v;
		pos+=lowbit(pos);
	}
}
inline int Sum(int x){
	register int res=0;
	while(x>0){
		res+=C[x];
		x-=lowbit(x);
	}
	return res;
}

int cnt[maxn];
int main(){
	register int i;
	int n,x,y;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		x++;
		cnt[Sum(x)]++;
		Add(x,1);
	}
	for(i=0;i<n;i++){
		printf("%d\n",cnt[i]);
	}
	return 0;
}

[洛谷 P1637]三元上升子序列

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

这个明显是用树状数组进行统计……然而是树状数组统计第一题……so sad

答案很有可能就超int,建议开long long(反正我这么做了)。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=30005;
int n;
struct BIT{
    int C[maxn];
    inline int lowbit(int x){
        return x&-x;
    }
    inline void Add(int p,int v){
        while(p<=n){
            C[p]+=v;
            p+=lowbit(p);
        }
    }
    inline int Sum(int x){
        register int ans=0;
        while(x>0){
            ans+=C[x];
            x-=lowbit(x);
        }
        return ans;
    }
    inline int Query(int l,int r){
        return Sum(r)-Sum(l-1);
    }
};

BIT T1,T2;
int A[maxn],A2[maxn];
int siz;
inline void InitLsh(){
    register int i;
    sort(A2+1,A2+n+1);
    siz=unique(A2+1,A2+n+1)-A2-1;
}
inline int GetLsh(int i){
    return lower_bound(A2+1,A2+siz+1,A[i])-A2;
}

int main(){
    register int i,left,right,temp;
    register long long ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        A2[i]=A[i];
    }
    InitLsh();
    for(i=1;i<=n;i++){
        T2.Add(GetLsh(i),1);
    }
    for(i=1;i<=n;i++){
        temp=GetLsh(i);
        T2.Add(temp,-1);
        left=T1.Sum(temp-1);
        right=T2.Query(temp+1,siz);
        ans+=((long long)left)*((long long)right);
        T1.Add(temp,1);
    }
    printf("%lld\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 1878]HH的项链

2016年8月18日 14:20 | Comments(0) | Category:题解 | Tags:

扫描线处女作TAT

直接离线,按左端点排序扫描。每个点要保存后继相同节点,每种元素第一次出现的位置都加1。然后扫描的时候有后继就给后继加。之后求区间和即可。

代码:

/**************************************************************
    Problem: 1878
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1344 ms
    Memory:8444 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=50001,maxm=200001;
int T[maxn];
int n;
inline int lowbit(int x){
    return x&(-x);
}
inline void update(int p,int v){
    while(p<=n){
        T[p]+=v;
        p+=lowbit(p);
    }
}
inline int query(int p){
    register int ans=0;
    while(p>0){
        ans+=T[p];
        p-=lowbit(p);
    }
    return ans;
}
 
struct Query{
    int l,r;
    int id;
    int ans;
    bool operator <(const Query& x) const{
        return l==x.l?r<x.r:l<x.l;
    }
};
Query Q[maxm];
bool cmp2(const Query& a,const Query& b){
    return a.id<b.id;
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
 
int next[maxn];
int A[maxn];
int pos[1000001];
int main(){
    int m,maxA=0;
    register int i,j;
    n=readint();
    for(i=1;i<=n;i++){
        A[i]=readint();
        maxA=max(maxA,A[i]);
    }
    for(i=n;i;i--){
        next[i]=pos[A[i]];
        pos[A[i]]=i;
    }
    for(i=1;i<=maxA;i++)
        if(pos[i])
            update(pos[i],1);
    m=readint();
    for(i=1;i<=m;i++){
        Q[i].l=readint();
        Q[i].r=readint();
        Q[i].id=i;
    }
    sort(Q+1,Q+1+m);
    register int tot=1;
    for(i=1;i<=m;i++){
        while(tot<Q[i].l){
            if(next[tot])
                update(next[tot],1);
            tot++;
        }
        Q[i].ans=query(Q[i].r)-query(Q[i].l-1);
    }
    sort(Q+1,Q+1+m,cmp2);
    for(i=1;i<=m;i++){
        writeint(Q[i].ans);
        putchar('\n');
    }
    return 0;
}