danihao123's Blog

[BZOJ 2190]仪仗队

这个题啊……有规律可循。

我们可以发现，关于答案[tex]a[/tex]有如下规律：

[tex]a+1=2\mul (\Sigma_{i=2}^{n-1}\varphi(i)+2)[/tex]

然后筛法求欧拉函数即可~~（我听说神犇们都用了杜教筛哎）~~

代码：

/**************************************************************
    Problem: 2190
    User: danihao123
    Language: C++
    Result: Accepted
    Time:28 ms
    Memory:976 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40005;
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int phi[maxn];
int n;
void sieve(){
    register int i,j;
    phi[1]=1;
    CUS_REP(i,2,n)
        if(!phi[i])
            for(j=i;j<=n;j+=i){
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}
 
int main(){
    register int i,ans=2;
    scanf("%d",&n);
    sieve();
    /*
    #ifdef DEBUG
    CUS_REP(i,1,n)
        printf("%d\n",phi[i]);
    #endif
    */
    CUS_REP(i,2,n-1)
        ans+=phi[i];
    printf("%d\n",ans*2-1);
    return 0;
}

[BZOJ 3531]旅行

发现自己好久没写树链剖分了……唉……

言归正传，这道题很容易想到的做法就是每种宗教开一个线段树，到各个宗教的线段树里面操作即可。

很可惜，直接开线段树的话肯定会MLE。我们可以考虑动态开点，对于不需要的点一律不开。这样内存消耗量就大减了。

注意一些细节：

查询时判断当前结点是不是NULL。
删除前最好判断一下这个结点是不是NULL吧，以防万一。
删除操作时，如果结点没有用了，就删。但是注意，记得delete前要把原指针设为NULL，直接delete会引起悬垂指针问题导致爆炸！

代码：

/**************************************************************
    Problem: 3531
    User: danihao123
    Language: C++
    Result: Accepted
    Time:10404 ms
    Memory:34872 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n;
namespace SegmentTree{
    struct Node{
        int sumv,maxv;
        Node *lc,*rc;
        Node(){
            sumv=maxv=0;
            lc=rc=NULL;
        }
        void maintain(){
            if(lc!=NULL){
                if(rc!=NULL){
                    sumv=lc->sumv+rc->sumv;
                    maxv=max(lc->maxv,rc->maxv);
                }else{
                    sumv=lc->sumv;
                    maxv=lc->maxv;
                }
            }else{
                if(rc!=NULL){
                    sumv=rc->sumv;
                    maxv=rc->maxv;
                }
            }
        }
    };
    Node* T[maxn];
    int p,v;
    void _Delete(Node* &o,int L,int R){
        if(o==NULL)
            return;
        if(L==R){
            Node *temp=o;
            o=NULL;
            delete temp;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Delete(o->lc,L,M);
            else
                _Delete(o->rc,M+1,R);
            if(o->lc==NULL && o->rc==NULL){
                Node *temp=o;
                o=NULL;
                delete temp;
            }else{
                o->maintain();
            }
        }
    }
    inline void Delete(int c,int pos){
        p=pos;
        _Delete(T[c],1,n);
    }
    void _Insert(Node* &o,int L,int R){
        if(o==NULL)
            o=new Node();
        if(L==R){
            o->sumv=o->maxv=v;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Insert(o->lc,L,M);
            else
                _Insert(o->rc,M+1,R);
        }
        o->maintain();
    }
    inline void Insert(int c,int pos,int value){
        p=pos;
        v=value;
        _Insert(T[c],1,n);
    }
    int ql,qr;
    int _query_max(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->maxv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans=max(ans,_query_max(o->lc,L,M));
        if(qr>M)
            ans=max(ans,_query_max(o->rc,M+1,R));
        return ans;
    }
    inline int query_max(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_max(T[c],1,n);
    }
    int _query_sum(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->sumv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans+=_query_sum(o->lc,L,M);
        if(qr>M)
            ans+=_query_sum(o->rc,M+1,R);
        return ans;
    }
    inline int query_sum(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_sum(T[c],1,n);
    }
};
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_tot=0;
inline void AddEdge(int u,int v){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
}
 
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
bool vis[maxn];
void dfs_1(int x,int father,int depth){
    vis[x]=true;
    fa[x]=father;
    dep[x]=depth;
    siz[x]=1;
    int i,temp,max_siz=0;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_1(temp,x,depth+1);
            siz[x]+=siz[temp];
            if(siz[temp]>max_siz){
                son[x]=temp;
                max_siz=siz[temp];
            }
        }
    }
}
int hld_cnt=0;
int rlg[maxn];
int d[maxn];
int tid[maxn],top[maxn];
void dfs_2(int x,int a){
    vis[x]=true;
    top[x]=a;
    tid[x]=++hld_cnt;
    SegmentTree::Insert(rlg[x],hld_cnt,d[x]);
    if(son[x])
        dfs_2(son[x],a);
    else
        return;
    int i,temp;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_2(temp,temp);
        }
    }
}
int query_max(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_max(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return max(SegmentTree::query_max(c,tid[top[x]],tid[x]),query_max(c,fa[top[x]],y));
}
int query_sum(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_sum(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return SegmentTree::query_sum(c,tid[top[x]],tid[x])+query_sum(c,fa[top[x]],y);
}
inline void Replace(int pos,int direction){
    int c=rlg[pos];
    SegmentTree::Delete(c,tid[pos]);
    SegmentTree::Insert(direction,tid[pos],d[pos]);
    rlg[pos]=direction;
}
inline void Update(int pos,int v){
    d[pos]=v;
    SegmentTree::Insert(rlg[pos],tid[pos],v);
}
 
int main(){
    register int i;
    int q,u,v;
    char buf[5];
    scanf("%d%d",&n,&q);
    REP_B(i,n){
        scanf("%d%d",&d[i],&rlg[i]);
    }
    REP_B(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs_1(1,0,1);
    memset(vis,0,sizeof(vis));
    dfs_2(1,1);
    while(q--){
        memset(buf,0,sizeof(buf));
        scanf("%s%d%d",buf,&u,&v);
        if(buf[0]=='C'){
            if(buf[1]=='W'){
                Update(u,v);
            }else{
                Replace(u,v);
            }
        }else{
            if(buf[1]=='M'){
                printf("%d\n",query_max(rlg[u],u,v));
            }else{
                printf("%d\n",query_sum(rlg[u],u,v));
            }
        }
    }
    return 0;
}

[BZOJ 1878]HH的项链

扫描线处女作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;
}

[BZOJ 2243]染色

树剖好题……

2243记录

这能说明几个问题：

人傻自带大常数
不看题解难AC

继续阅读

[BZOJ 2190]仪仗队

[BZOJ 3531]旅行

[BZOJ 1878]HH的项链

[BZOJ 2243]染色

danihao123

搜索

分类

标签云

最新评论

最新留言

神犇的Blog

RSS

功能

计数器