danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26240

[BZOJ 1798]维护序列

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

万年不更的zzs出现了……

这个题以前竟然没做……近几天做了一下,首交竟然unAC……看样子是我真不会线段树了。

这题不难,唯一需要注意的是乘法标记对加法标记也有影响,而且下传要乘法优先。

代码(警告:此代码exciting):

/**************************************************************
    Problem: 1798
    User: danihao123
    Language: C++
    Result: Accepted
    Time:7696 ms
    Memory:10980 kb
****************************************************************/
 
#include <cstdio>
typedef long long ll;
const int maxn=100005;
ll ha;
struct Node{
    ll sumv;
    int L,R;
    ll addv,mulv;
    Node *lc,*rc;
    Node(ll v,int pos){
        sumv=v%ha;
        addv=0;
        mulv=1;
        L=R=pos;
        lc=rc=NULL;
    }
    Node(Node *l,Node *r,int Le,int Ri){
        sumv=0;
        addv=0;
        mulv=1;
        L=Le;
        R=Ri;
        lc=l;
        rc=r;
    }
    void paint_add(ll v){
        v=v%ha;
        addv=(addv+v)%ha;
        ll add_v=(v*((R-L+1)%ha))%ha;
        sumv=(sumv+add_v)%ha;
    }
    void paint_mul(ll v){
        v=v%ha;
        addv=(addv*v)%ha;
        mulv=(mulv*v)%ha;
        sumv=(sumv*v)%ha;
    }
    void maintain(){
        if(lc!=NULL && rc!=NULL){
            sumv=(lc->sumv+rc->sumv)%ha;
        }
    }
    void pushdown(){
        if(mulv!=1){
            if(lc!=NULL){
                lc->paint_mul(mulv);
            }
            if(rc!=NULL){
                rc->paint_mul(mulv);
            }
            mulv=1;
        }
        if(addv!=0){
            if(lc!=NULL){
                lc->paint_add(addv);
            }
            if(rc!=NULL){
                rc->paint_add(addv);
            }
            addv=0;
        }
    }
};
 
ll A[maxn];
void build_tree(Node* &o,int L,int R){
    if(L==R){
        o=new Node(A[L],L);
    }else{
        int M=L+(R-L)/2;
        Node *lc,*rc;
        build_tree(lc,L,M);
        build_tree(rc,M+1,R);
        o=new Node(lc,rc,L,R);
        o->maintain();
    }
}
Node *root;
int ql,qr;
ll v;
ll query_sum(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        return o->sumv;
    }else{
        int M=L+(R-L)/2;
        ll ans=0;
        if(ql<=M){
            ans=(ans+query_sum(o->lc))%ha;
        }
        if(qr>M){
            ans=(ans+query_sum(o->rc))%ha;
        }
        return ans;
    }
}
void update_add(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        o->paint_add(v);
    }else{
        int M=L+(R-L)/2;
        if(ql<=M){
            update_add(o->lc);
        }
        if(qr>M){
            update_add(o->rc);
        }
        o->maintain();
    }
}
void update_mul(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        o->paint_mul(v);
    }else{
        int M=L+(R-L)/2;
        if(ql<=M){
            update_mul(o->lc);
        }
        if(qr>M){
            update_mul(o->rc);
        }
        o->maintain();
    }
}
 
int main(){
    register int i;
    int n,m,op;
    scanf("%d%lld",&n,&ha);
    // ha=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    build_tree(root,1,n);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d%d",&op,&ql,&qr);
        if(ha==1){
            if(op==3){
                puts("0");
            }else{
                scanf("%lld",&v);
            }
            continue;
        }
        if(op==1){
            scanf("%lld",&v);
            update_mul(root);
        }else{
            if(op==2){
                scanf("%lld",&v);
                update_add(root);
            }else{
                printf("%lld\n",query_sum(root));
            }
        }
    }
    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;
}

[BZOJ 3306]树

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

这个题其他操作都不难(DFS序+线段树水过),就是换根有点头疼……直接做的话要TopTree吧。

不过我们考虑用DFS序+线段树的“偷懒”做法。每次查询的时候考虑当前的根,如果这个根最初不在x的子树中,那么对目前的查询值没有影响;如果就是x,那么整个树都是x的子树;如果是x的某个后代,那么整个树里除了他的后代所在额这颗子树以外的所有部分全部变成了x的子树(试着翻转一下就明白了)。判断后代祖先以及在哪个子树这些东西可以用倍增LCA高效实现,问题就这样简单了。

代码:

/**************************************************************
    Problem: 3306
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2308 ms
    Memory:17544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
#define SEG_STD int o,int L,int R
#define MAKE_MID int M=L+(R-L)/2
// #define MAKE_CLD int lc=o<<1,rc=o<<1|1
#define LCH o<<1,L,M
#define RCH o<<1|1,M+1,R
int n;
int minv[maxnode];
int A[maxn];
void maintain(int o){
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(SEG_STD){
    if(L==R){
        minv[o]=A[L];
    }else{
        MAKE_MID;
        build_tree(LCH);
        build_tree(RCH);
        maintain(o);
    }
}
int ql,qr;
int query(SEG_STD){
    if(ql<=L && R<=qr){
        return minv[o];
    }else{
        MAKE_MID;
        int ans=INF;
        if(ql<=M)
            ans=min(ans,query(LCH));
        if(qr>M)
            ans=min(ans,query(RCH));
        return ans;
    }
}
int p,v;
void update(SEG_STD){
    if(L==R){
        minv[o]=v;
    }else{
        MAKE_MID;
        if(p<=M)
            update(LCH);
        else
            update(RCH);
        maintain(o);
    }
}
inline int query(int l,int r){
    if(l<1 || l>n || r<1 || r>n)
        return INF;
    ql=l;
    qr=r;
    return query(1,1,n);
}
inline void update(int pos,int value){
    p=pos;
    v=value;
    update(1,1,n);
}
 
int first[maxn];
int next[maxn],to[maxn];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int d[maxn];
int tid[maxn];
int anc[maxn][19],dep[maxn];
int siz[maxn];
int dfs_clk=0;
void dfs(int x,int fa,int depth){
    dfs_clk++;
    tid[x]=dfs_clk;
    A[dfs_clk]=d[x];
    anc[x][0]=fa;
    dep[x]=depth;
    siz[x]=1;
    int i;
    for(i=first[x];i;i=next[i]){
        dfs(to[i],x,depth+1);
        siz[x]+=siz[to[i]];
    }
}
void process(){
    register int i,j;
    for(j=1;(1<<j)<n;j++)
        for(i=1;i<=n;i++)
            if(anc[i][j-1]!=-1)
                anc[i][j]=anc[anc[i][j-1]][j-1];
}
int root;
bool isAnc(int x){
    register int p=root,j;
    if(dep[p]<dep[x])
        return false;
    for(j=18;j>=0;j--)
        if(dep[p]-(1<<j)>=dep[x] && anc[p][j]!=-1)
            p=anc[p][j];
    return p==x;
}
int findAnc(int x,int y){
    register int j;
    for(j=18;j>=0;j--)
        if(dep[y]-dep[x]-(1<<j)>0 && anc[y][j]!=-1)
            y=anc[y][j];
    return y;
}
 
int getAns(int x){
    if(x==root){
        return query(1,n);
    }else{
        if(isAnc(x)){
            register int t=findAnc(x,root);
            register int l=tid[t],r=tid[t]+siz[t]-1;
            return min(query(1,l-1),query(r+1,n));
        }else{
            return query(tid[x],tid[x]+siz[x]-1);
        }
    }
}
 
int main(){
    int q,x,f;
    register int i;
    char buf[3];
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++){
        scanf("%d%d",&f,&d[i]);
        if(!f){
            root=i;
        }else{
            AddEdge(f,i);
        }
    }
    memset(anc,-1,sizeof(anc));
    dfs(root,-1,0);
    process();
    build_tree(1,1,n);
    while(q--){
        scanf("%s%d",buf,&x);
        if(buf[0]=='V'){
            scanf("%d",&f);
            update(tid[x],f);
        }else{
            if(buf[0]=='Q'){
                printf("%d\n",getAns(x));
            }else{
                root=x;
            }
        }
    }
    return 0;
}

[BZOJ 3339]Rmq Problem

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

万恶的标题党啊~

这个题明显扫描线辣……但是怎么扫呢?

我们可以考虑对于每个前缀区间[tex][1,r][/tex]先求出他们的[tex]mex[/tex]值,然后用线段树维护。

从[tex][l,r][/tex]转移到[tex][l+1,r][/tex]时,需要将[tex][l,next[l]-1][/tex]([tex]next[l][/tex]是下一个和[tex]l[/tex]具有相同值的位置)中的所有大于[tex]A[l][/tex]([tex]l[/tex]的值)的值全部变为[tex]A[l][/tex]。但是这一步怎么做啊……难道要用Segment Beats?

答案是否定的。注意到我们真正需要的只是叶子结点,所以其他非叶子结点的最小值全部弄成无限大,然后这样做就可以把最小值当做标记来弄了……非常精巧。

代码:

/**************************************************************
    Problem: 3339
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1988 ms
    Memory:10396 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=200005,INF=0x7f7f7f7f;
const int maxnode=maxn*4;
int A[maxn];
int minv[maxnode];
void build_tree(int o,int L,int R){
    if(L==R){
        minv[o]=A[L];
    }else{
        int M=L+(R-L)/2;
        minv[o]=INF;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
    }
}
inline void paint(int o,int v){
    minv[o]=min(minv[o],v);
}
inline void pushdown(int o){
    paint(o<<1,minv[o]);
    paint(o<<1|1,minv[o]);
    minv[o]=INF;
}
int pos;
int query(int o,int L,int R){
    if(L==R)
        return minv[o];
    if(minv[o]<INF)
        pushdown(o);
    int M=L+(R-L)/2;
    if(pos<=M)
        return query(o<<1,L,M);
    else
        return query(o<<1|1,M+1,R);
}
int ql,qr,v;
void update(int o,int L,int R){
    if(ql<=L && R<=qr){
        paint(o,v);
    }else{
        if(minv[o]<INF)
            pushdown(o);
        int M=L+(R-L)/2;
        if(ql<=M)
            update(o<<1,L,M);
        if(qr>M)
            update(o<<1|1,M+1,R);
    }
}
 
inline int readint(){
    register int x=0;
    register char c;
    fread(&c,1,1,stdin);
    while(!isdigit(c))
        fread(&c,1,1,stdin);
    while(isdigit(c)){
        x=x*10+c-'0';
        fread(&c,1,1,stdin);
    }
    return x;
}
int buf[21];
inline void putint(int x){
    register int i,p=0;
    if(!x){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
 
bool vis[maxn];
int last[maxn],next[maxn];
struct Query{
    int id;
    int l,r;
    int ans;
};
bool cmp1(const Query& x,const Query& y){
    if(x.l==y.l)
        return x.r<y.r;
    else
        return x.l<y.l;
}
bool cmp2(const Query& x,const Query& y){
    return x.id<y.id;
}
Query QS[maxn];
int V[maxn];
int main(){
    int n,q;
    register int i,l=1,k=0;
    n=readint();
    q=readint();
    for(i=1;i<=n;i++){
        V[i]=readint();
        vis[V[i]]=true;
        if(k==V[i])
            while(vis[k])
                k++;
        A[i]=k;
    }
    build_tree(1,1,n);
    for(i=n;i>=1;i--){
        if(!last[V[i]])
            next[i]=n+1;
        else
            next[i]=last[V[i]];
        last[V[i]]=i;
    }
    for(i=1;i<=q;i++){
        QS[i].id=i;
        QS[i].l=readint();
        QS[i].r=readint();
    }
    sort(QS+1,QS+1+q,cmp1);
    for(i=1;i<=q;i++){
        while(l<QS[i].l){
            ql=l;
            qr=next[l]-1;
            v=V[l];
            update(1,1,n);
            l++;
        }
        pos=QS[i].r;
        QS[i].ans=query(1,1,n);
    }
    sort(QS+1,QS+1+q,cmp2);
    for(i=1;i<=q;i++){
        putint(QS[i].ans);
    }
    return 0;
}

[BZOJ 1756]小白逛公园

2016年7月18日 19:22 | Comments(0) | Category:题解 | Tags:

这题是很经典的线段树题。

我们可以发现最长子序列或跨越中点,或不跨越中点。若不跨越则肯定在左子或右子中,跨越则是左子最大后缀和和右子最大前缀和之和。问题便迎刃而解。(当然,求区间最大前缀/后缀和要用上区间和)

需注意此题可能会出现a>b!

代码:

/**************************************************************
    Problem: 1756
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2604 ms
    Memory:49648 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500001;
struct Node{
    int L,R;
    int maxP,maxS,ans,sum;
};
Node Tree[maxn*4];
int A[maxn];
void merge(Node& O,Node& LC,Node& RC){
    O.sum=LC.sum+RC.sum;
    O.maxP=max(LC.maxP,LC.sum+RC.maxP);
    O.maxS=max(RC.maxS,RC.sum+LC.maxS);
    O.ans=max(max(LC.ans,RC.ans),LC.maxS+RC.maxP);
}
void maintain(int o){
    Node& O=Tree[o],LC=Tree[o<<1],RC=Tree[o<<1|1];
    merge(O,LC,RC);
}
void build_tree(int o,int L,int R){
    Node& O=Tree[o];
    O.L=L;
    O.R=R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=A[L];
    }else{
        int M=L+(R-L)/2;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
        maintain(o);
    }
}
void update(int o,int p,int v){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=v;
    }else{
        int M=L+(R-L)/2;
        if(p<=M)
            update(o<<1,p,v);
        else
            update(o<<1|1,p,v);
        maintain(o);
    }
}
int ql,qr;
Node query(int o){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(ql<=L && R<=qr){
        return Tree[o];
    }
    int M=L+(R-L)/2;
    Node ANS,LC,RC;
    if(ql<=M){
        LC=query(o<<1);
        if(qr>M){
            RC=query(o<<1|1);
            merge(ANS,LC,RC);
            return ANS;
        }else{
            return LC;
        }
    }else{
        RC=query(o<<1|1);
        return RC;
    }
}
int main(){
    int n,m;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&A[i]);
    build_tree(1,1,n);
    int k,a,b;
    Node ans;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&k,&a,&b);
        if(k&1){
            if(a>b)
                swap(a,b);
            ql=a;
            qr=b;
            ans=query(1);
            printf("%d\n",ans.ans);
        }else{
            update(1,a,b);
        }
    }
    return 0;
}

[BZOJ 3211]花神游历各国

2016年3月27日 22:02 | Comments(0) | Category:题解 | Tags:

这题和3038几乎一样啊……

但是注意有的喜欢度可能为0,这种情况不处理的话时间效率duangduangduang……

代码:

[BZOJ 3038]上帝造题的七分钟2

2016年3月27日 18:05 | Comments(0) | Category:题解 | Tags:

这题也真是的……

其实也不难,开多了就成1了,成1了再怎么开也是1……所以暴力单点修改+配合标记乱搞搞就行了

代码:

[CodeVS 1191]数轴染色

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

刷水体哎~

线段树水题哎~

代码: