首页 > 代码库 > 暑假集训day8

暑假集训day8

其实这是昨天的事了。(现在时间回到一天前)

RMQ。。这个就不介绍了,应该都知道

RMQ with shift(UVa 12299)

这题就简单线段树跑一下就好了,本人巨弱不会zkw。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100010;
const int INF=947483647;
inline int read(){
    int t=1,num=0;char c=getchar();
    while(c>9||c<0){if(c==-)t=-1;if(c==\n)return INF;c=getchar();}
    while(c>=0&&c<=9){num=(num<<3)+(num<<1)+c-0;c=getchar();}
    return num*t;
}
int n,q,a[maxn],t[3*maxn];
void build(int ro,int l,int r){
    if(l==r)t[ro]=a[l];
    else{
        int mid=(l+r)/2;
        build(ro*2,l,mid);build(ro*2+1,mid+1,r);
        t[ro]=min(t[ro*2],t[ro*2+1]);
    }
}
int ask(int ro,int l,int r,int x,int y){
    if(x>r||y<l) return INF;
    if(x<=l&&r<=y) return t[ro];
    int mid=(l+r)/2;
    return min(ask(ro*2,l,mid,x,y),ask(ro*2+1,mid+1,r,x,y));
}
void change(int ro,int l,int r,int x,int add){
    if(l==r){if(x==l){t[ro]=add;}return;}
    int mid=(l+r)/2;
    if(x<=mid)change(ro*2,l,mid,x,add);
    else  change(ro*2+1,mid+1,r,x,add);
    t[ro]=min(t[ro*2],t[ro*2+1]);
}
int main()
{
    n=read();q=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    for(int i=1;i<=q;i++){
        char c=getchar();while(c!=s&&c!=q)c=getchar();
        if(c==q){
            int x=read(),y=read();
            printf("%d\n",ask(1,1,n,x,y));
        }
        else{
            int x=read(),y=read();
            int f=a[x];
            while(y!=INF){
                change(1,1,n,x,a[y]);a[x]=a[y];
                x=y;y=read();
            }change(1,1,n,x,f);a[x]=f;
        }
    }
    return 0;
}

树的统计(bzoj_1036)

就是树链剖分了,模板题。

这题调了半天、、发现swap(t1,t2)变成swap(t1,t1)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=30010,INF=947483647;
inline int read(){
    int t=1,num=0;char c=getchar();
    while(c>9||c<0){if(c==-)t=-1;c=getchar();}
    while(c>=0&&c<=9){num=(num<<1)+(num<<3)+c-0;c=getchar();}
    return num*t;
}
struct yzy{int c[2];}t[3*N];vector<int>biao[N];
int n,q,a[N],val[2]={0,-INF},fa[N],dep[N],son[N],size[N],top[N],root,k;
void dfs1(int x,int f,int d){
    dep[x]=d;fa[x]=f;size[x]=1;son[x]=0;
    for (int i=0;i<biao[x].size();i++) {  
        int y=biao[x][i];if(y==f)continue;
        dfs1(y,x,d+1);size[x]+=size[y];
        if(size[y]>size[son[x]])son[x]=y;
    }
}
int num=0,id[N];
void dfs2(int x,int tp){
    id[x]=++num;top[x]=tp;
    if(son[x])dfs2(son[x],tp);
    for(int i=0;i<biao[x].size();i++){
        int y=biao[x][i];if(y!=son[x]&&y!=fa[x])dfs2(y,y);
    }
}
void build(int ro,int l,int r){
    if(l==r){t[ro].c[0]=t[ro].c[1]=a[l];return;}
    int mid=(l+r)>>1;
    build(ro<<1,l,mid);build((ro<<1)+1,mid+1,r);
    t[ro].c[0]=t[ro<<1].c[0]+t[(ro<<1)+1].c[0];
    t[ro].c[1]=max(t[ro<<1].c[1],t[(ro<<1)+1].c[1]);
}
int ask(int ro,int l,int r,int x,int y){
    if(x>r||y<l)return val[k];if(x<=l&&r<=y)return t[ro].c[k];
    int mid=(l+r)>>1;
    if(!k)return (ask(ro<<1,l,mid,x,y)+ask((ro<<1)+1,mid+1,r,x,y));
    return max(ask(ro<<1,l,mid,x,y),ask((ro<<1)+1,mid+1,r,x,y));
}
void change(int ro,int l,int r,int x,int add){
    if(l==r){if(x==l){t[ro].c[0]+=add;t[ro].c[1]+=add;}return;}
    int mid=(l+r)>>1;
    if(x<=mid)change(ro<<1,l,mid,x,add);
    else change((ro<<1)+1,mid+1,r,x,add);
    t[ro].c[0]=t[ro<<1].c[0]+t[(ro<<1)+1].c[0];
    t[ro].c[1]=max(t[ro<<1].c[1],t[(ro<<1)+1].c[1]);
}
int solve(int x,int y){
    int t1=top[x],t2=top[y],ans=val[k];
    while(t1!=t2){
        if(dep[t1]<dep[t2]){swap(t1,t2);swap(x,y);}
        if(k)ans=max(ask(1,1,n,id[t1],id[x]),ans);
        else ans+=ask(1,1,n,id[t1],id[x]);
        x=fa[t1];t1=top[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    if(k)ans=max(ask(1,1,n,id[x],id[y]),ans);
    else ans+=ask(1,1,n,id[x],id[y]);
    return ans;
}
int main()
{
    n=read();for(int i=1;i<n;i++){
        int x=read(),y=read();
        biao[x].push_back(y);biao[y].push_back(x);
    }dfs1(1,0,1);dfs2(1,1);
    for(int i=1;i<=n;i++)a[id[i]]=read();
    build(1,1,n);q=read();
    for(int i=1;i<=q;i++){
        char c=getchar();
        while(c!=H&&c!=M&&c!=S)c=getchar();
        int x=read(),y=read();
        if(c==H){change(1,1,n,id[x],y-a[id[x]]);a[id[x]]=y;continue;}
        else if(c==M)k=1;else k=0;
        printf("%d\n",solve(x,y));
    }
    return 0;
}

本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。

暑假集训day8