CXJY-Day 2

Axell Jul 30, 2019

写在前面

又是新的一天，又被虐爆啦
T1打了好久的线段树，完全是正解。。。结果线段树打错了，40分。。。暴力都能水100；大哭
然后有日常讲了数据结构和好多题。。。慢慢消化吧

愤怒的小鸟（bird）

【题目描述】

小A最近迷上了愤怒的小鸟这一款游戏，很快就通关了，但是他还是想要玩这个游戏，而且因为学业繁忙，他每天只能玩一关，有时候因为太忙了，他甚至来不及挑选自己最喜欢的关卡来玩，只好随便点一个他已经玩过了的关卡玩，但这并不能够减轻他对于愤怒的小鸟这款游戏的喜爱。
但是有一天，他的平板中病毒了，数据被毁了大半，愤怒的小鸟的通关数据也没能够避免这一场灾祸，只留下了中间一段时间的通关记录，所以小A现在想要知道他如果想要重新通关，他要从哪一关打起（该关要是小A第一个没有通关记录的关卡）。
然而小A也不知道中间留下了哪段时间的通关记录，所以只好请你对于每种情况求出他要从哪一关打起，然后将这个值求和告诉小A。
由于有教学关的存在，所以有第0关。

【输入数据】

第一行一个整数n表示之前小A玩了多少天愤怒的小鸟。
接下来一行n个整数表示每一天小A玩的是哪一关。

【输出数据】

一个整数，表示每种情况下小A需要打的关卡的编号之和。

【样例输入】

10
1 4 2 3 0 5 2 3 4 1

【样例输出】

【数据范围】

对于30%的数据，$n≤5000$。
对于另30%的数据，每天玩的关卡集合包括$[0,n-1]$的所有整数，即每天玩的关卡序列为一个$[0,n-1]$的排列。
对于100%的数据，$n≤100000$。

题解

首先以1为左端点,求出每个右端点的区间的mex值,这个值显然是递增的。
然后考虑删除左端点对后续区间带来的影响。
设当前删掉第×个数,y为第一个与第x个数相等的数的位置。
则y及以后的区间中,$mex$值不发生改变(因为数的集合没有发生改变)。
而x到y的区间中,$mex$值大于$a_x$的会变成$a_x$(因为这些区间不包含$a_x$，通过二分查找),而这些区间也会是连续的。
然后就是用线段树来维护这些了。
要支持区间更新,区间求和,区间查询 push_down操作必须在return语句后完成，否则数组会越界，还有懒惰标记的线段树好不熟练啊

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lc (rt<<1)
#define rc ((rt<<1)|1)
struct node{
    ll v,tag;
}tr[400005];
int n,a[100005],b[100005];
ll ans;

void up(int rt){
    tr[rt].v=tr[lc].v+tr[rc].v;
}
void down(int rt,int l,int r){
    if (tr[rt].tag==-1) return;
    tr[lc].tag=tr[rc].tag=tr[rt].tag;
    int mid=(l+r)>>1;
    tr[lc].v=(ll)(mid-l+1)*tr[rt].tag;
    tr[rc].v=(ll)(r-mid)*tr[rt].tag;
    tr[rt].tag=-1;
}

void build(int rt,int l,int r){
    tr[rt].tag=-1;
    if (l==r){
        tr[rt].v=b[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid); build(rc,mid+1,r);
    up(rt);
}

ll query(int wl,int wr,int rt,int l,int r){
    if (l==wl && r==wr){
        return tr[rt].v;
    }
    down(rt,l,r);
    int mid=(l+r)>>1;
    if (wr<=mid) return query(wl,wr,lc,l,mid);
    else if (wl>mid) return query(wl,wr,rc,mid+1,r);
    return query(wl,mid,lc,l,mid)+query(mid+1,wr,rc,mid+1,r);
    up(rt);
}

void change(int wl,int wr,int v,int rt,int l,int r){
    if (l==wl && r==wr){
        tr[rt].tag=v;
        tr[rt].v=(ll)(r-l+1)*v;
        return;
    }
    down(rt,l,r);
    int mid=(l+r)>>1;
    if (wr<=mid) change(wl,wr,v,lc,l,mid);
    else if (wl>mid) change(wl,wr,v,rc,mid+1,r);
    else change(wl,mid,v,lc,l,mid),change(mid+1,wr,v,rc,mid+1,r);
    up(rt);
}

set <int> ss[100005];

int main(){
    freopen("bird.in","r",stdin);
    freopen("bird.out","w",stdout);
    cin>>n;
    set <int> s;
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        s.insert(i-1);
        ss[a[i]].insert(i);
    }
    for (int i=1;i<=n;++i){
        s.erase(a[i]);
        if (s.size()) b[i]=*s.begin();
        else b[i]=n;
    }
    build(1,1,n);
    for (int i=1;i<=n;++i){
        ans+=query(i,n,1,1,n);
        if (i==n) continue;
        int p=a[i];
        ss[p].erase(i);
        int nxt;
        if (ss[p].size()) nxt=*ss[p].begin();
        else nxt=n+1;
        int L=i+1,R=nxt-1,ANS=-1;
        while (L<=R){
            int mid=(L+R)>>1;
            if (query(mid,mid,1,1,n)>p){
                ANS=mid;
                R=mid-1;
            }else{
                L=mid+1;
            }
        }
        if (ANS==-1) continue;
        change(ANS,nxt-1,p,1,1,n);
    }
    cout<<ans<<endl;
    return 0;
}

城镇规划（design）

【题目描述】

小A最近在玩《都市：天际线》这款游戏，他在不断地建设着自己的城市（比如说修路盖房这种）。
但是一个没有贸易的城市是没有灵魂的，所以小A的城市中有许许多多的贸易来往，给这个城市带来源源不断的资金。
然而小A为了展现自己高超的游戏技巧，给自己打了一个增加游戏难度的mod，使得贸易的难度陡然上升。
在这个mod中，城市中的每一条路都有一个颜色C，假设贸易经过的路径序列为Ci(i=1,2,…,n)，那么需要满足的路径才能够成功完成这个贸易，否则就会出现诸如强盗打劫货物，货车翻车等事件导致贸易失败。
但是小A其实并没有100%计算正确的信心，所以他希望你能一直帮忙告诉他，他下一次准备进行的从A点到B点的贸易是否能够成功，由于小A的城市在不断施工，所以随时可能有一条路被建成。

【输入数据】

第一行三个整数n，m，q，表示关键点个数，原始边数和操作（询问）次数。
接下来m行每行3个整数x，y，c，表示x与y之间有一条颜色为c的边。
接下来q行，每行有一个字符。
如果字符为+，那么接下来有3个整数x，y，c，表示增加一条x与y之间的颜色为c的边。
如果字符为?，那么接下来有2个整数x，y，表示询问从x点到y点的贸易当前能否成功。

【输出数据】

对于每个?的询问，输出”Yes”或”No”表示该次贸易能否成功。

【样例输入】

【样例输出】

Yes
No
Yes

【数据范围】

对于20%的数据，$1≤n,m,q≤8$。对于另20%的数据，$1≤n,m,q≤1000$。对于另20%的数据，颜色仅有$1,2$两种。对于另20%的数据，颜色范围为$[1,100]$。对于100%的数据，$1≤n,m,q≤100000$,边的颜色范围为$[1,n]$。

题解

把通过合法路径互相可达的点放在同一个并查集内，并查集里放一个set，储存该集合内通过若干2步+1/0步（即最后一步）可以到达的点集
每次加一条边时（x，y，c），可以找到任意一个y出发，颜色为c的边到达的终点，将x，z集合合并，同理把y和另一个值合并，同时把y加到fx的set中，表示fx所在集合的所有点都能一步到达y
在路径压缩时，把该点的set与他的父亲合并。
每次合并时，把两个点的set启发式合并（小的set合并到大的set里）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m,q;
char s[5];
map <int,int> mp[100005];
set <int> st[100005];
int f[100005];

int get(int x){
    if (f[x]==x) return x;
    return f[x]=get(f[x]);
}

void merge(int a,int b){
    int x=get(a),y=get(b);
    if (x==y) return; //注意这里要return，否则st[x].clear会不小心把要用的区间清掉
    if (st[x].size()>st[y].size()) swap(x,y);
    f[x]=y; st[y].insert(st[x].begin(),st[x].end());
    st[x].clear();
}

void add(int x,int y,int c){
    int xx=get(x),yy=get(y);
    st[xx].insert(y); st[yy].insert(x);
    if (mp[y].count(c)!=0){
        int z=mp[y][c];
        merge(x,z);
    }else mp[y][c]=x;
    if (mp[x].count(c)!=0){
        int z=mp[x][c];
        merge(y,z);
    }else mp[x][c]=y;
}

int main(){
    freopen("design.in","r",stdin);
    freopen("design.out","w",stdout);
    cin>>n>>m>>q;
    for (int i=1;i<=n;++i) st[i].insert(i),f[i]=i;
    for (int i=1;i<=m;++i){
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
    }
    while (q--){
        int x,y;
        scanf("%s%d%d",s+1,&x,&y);
        if (s[1]=='+'){
            int c;
            scanf("%d",&c);
            add(x,y,c);
        }else{
            int xx=get(x);
            if (st[xx].count(y) || get(x)==get(y)){
                puts("Yes");
            }else puts("No");
        }
    }
    return 0;
}

打气球（balloon）

【题目描述】

小A放暑假了，去他妈妈开的幼儿园帮他妈妈一起照顾小朋友，给他的妈妈减轻一些负担。
小朋友们很皮，吹了很多个气球，并把它们排成了一排，小朋友们叫小A来打爆一些气球，听着气球爆炸的声音，他们十分地开心，甚至自己也想要来，但是小A以安全为名拒绝了他们。
具体来说，一个小朋友i变得十分开心，需要序号为$[Li,Ri]$的气球被全部打掉，而小A每次只会打爆一个气球，小A想要更好地使这些小朋友们变得快乐，就想要知道，每次他打爆一个气球后，有多少小朋友是快乐的。

【输入数据】

第一行三个整数n，m，type表示气球的个数，小朋友的个数，数据种类。
接下来m行两个整数L，R表示当序号为$[L,R]$的气球被全部打空后，这个小朋友会十分开心。
接下来一行一个整数q，表示小A打爆了多少个气球。
接下来q行每行一个整数x，表示小A这次打爆了第x个气球，数据保证第x个气球还没有被打爆，如果type=0，那么x要异或上上一次回答的答案（第一次默认答案为0）。

【输出数据】

输出q行每行一个数字表示这次打爆气球后有多少小朋友十分开心。

【样例输入】

【样例输出】

【数据范围】

有30%的数据，$n,m,q≤1000$。另有30%的数据，$Ri-Li+1≤10$。另有20%的数据，$type=1$。其余的$type=0$。对于100%的数据，$n,m,q≤100000$。

题解

60% 暴力
80% 离线，记录每个点爆炸的时间，对于每个孩子求出$[L,R]$的最小值即可
100%
SOL1：这样就需要能够得到一个点所在的连续被打爆的气球的区间的左右端点。
可以做一个链表,要求连续被打爆的最长区间,其实就是找当前要被打爆的这个气球的左右第一个没有爆的气球。
于是一个可删除双向链表就可以维护这个信息了。
然后假设最长区间左右端点为L，R，被打爆的气球序号为X,求解其实就是求左端点在$[L,X]$,右端点在$[X,R]$区间的个数。
树套树即可。
SOL2：得想办法把我无敌的线段树合并用起来。
一开始把所有区间都挂在右端点上,即在那个线段树中把左端点的值加一。
用并查集来维护一个区间的线段树最后都合并到了哪一个节点。
然后想要查询包含x的区间,就先把x的线段树与右边的并查集的根的那棵线段树合并,然后查询$[L,x]$的和,然后把左右两边的线段树合并,并查集也合并
如果不想要用并查集,可以把线段树都合并到区间的右端点那边,这样的话也可以进行维护(但是还是要用上面的链表那样)。
SOL3：其实这道题也可以用线段树做，把每个孩子的$[L,R]$分到并查集上（即把一个区间分成不多于logn个小区间），定义线段树上个节点权值为对应区间的长度（R-L+1），孩子的权值为包含的区间数，每个点操作时，把包含它的各个区间权值-1，权值为0时即该区间被覆盖，把该区间对应的孩子权值-1，如果减到0，ans+1
代码对应SOL3

#include <bits/stdc++.h>
using namespace std;
#define lc (rt<<1)
#define rc ((rt<<1)|1)
typedef long long ll;

int n,m,ty,q,ans;
int tr[400005],tv[400005],cnt,cc[100005];
vector <int> v[2000005];

void update(int wl,int wr,int index,int rt,int l,int r){
    if (l==wl && r==wr){
        if (!tr[rt]) tr[rt]=++cnt;
        v[tr[rt]].push_back(index);
        cc[index]++; tv[rt]=r-l+1;
        return;
    }
    int mid=(l+r)>>1;
    if (wr<=mid) update(wl,wr,index,lc,l,mid);
    else if (wl>mid) update(wl,wr,index,rc,mid+1,r);
    else update(wl,mid,index,lc,l,mid),update(mid+1,wr,index,rc,mid+1,r);
}

void calc(int p,int rt,int l,int r){
    tv[rt]--;
    if (tv[rt]==0){
        if (tr[rt]==0) return;
        for (int i=0;i<v[tr[rt]].size();++i){
            int a=v[tr[rt]][i];
            cc[a]--;
            if (cc[a]==0){
                // cout<<a<<endl;
                ans++;
            }
        }
    }
    if (l==r) return;
    int mid=(l+r)>>1;
    if (p<=mid) calc(p,lc,l,mid);
    else calc(p,rc,mid+1,r);
}

int main(){
    freopen("balloon.in","r",stdin);
    freopen("balloon.out","w",stdout);
    cin>>n>>m>>ty;
    for (int i=1;i<=m;++i){
        int l,r;
        scanf("%d%d",&l,&r);
        update(l,r,i,1,1,n);
    }
    cin>>q;
    int la=0;
    while (q--){
        int x;
        scanf("%d",&x);
        if (!ty) x^=la;
        calc(x,1,1,n);
        la=ans;
        printf("%d\n",ans);
    }
    return 0;
}

其他

ZKW线段树

习题

luogu1438
BZOJ2789 POI2012 Letters
CF460C Present
BZOJ3524 POI2014 Couriers
BZOJ2959 长跑
BZOJ3744 Gty的妹子序列
BZOJ4320 Homework

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/cxjy-day-2/