长沙十天集训总结

非map形式的离散化

以前对于一些简单的整数离散化，总喜欢用$map$和一个递增变量来离散化，用着很方便，但是在这次考试中却因为$map$自带的巨大常数而TLE了。

于是在网上去找了一个非$map$形式的离散化方法，把题AC了，时间复杂度也很优。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000;
int aaa[5000],t[5000]; 
int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> aaa[i];
        t[i] = aaa[i];
    }
    sort(t+1,t+1+n);
    int m = unique(t+1,t+1+n) - t - 1;
    for(int i=1;i<=n;i++){
        aaa[i] = lower_bound(t+1,t+1+m,aaa[i]) - t;
    }
    for(int i=1;i<=n;i++){
        cout << aaa[i] << " ";
    }
    return 0;
}

这里的$t$数组就是辅助离散化用的，先将t数组排序去重然后将原数组$aaa$进行离散化，这个方法保证了当$aaa$里面元素大小相同的时候，离散化到的数大小也相同

线段树求逆序对

这次长沙集训有一道题需要求出一个序列中每个数对应的逆序对个数，不再像之前所解决的问题那样只需要求出总逆序对个数就可以了。于是以前只关注过$merge_sort$求逆序对个数的我这次就吃了大亏

特意去学习了一下怎么用线段树来求每个位置上的数对总逆序对个数贡献数怎么求，当然用到了类似桶的思想，将原数组通过上述非$map$形式离散化方法进行了离散化。对整个数组从后往前操作，线段树记录当前每个数出现的次数。当想求当前这个数有多少逆序对的时候，只需要询问线段树当前比要求这个数小的数有多少个就是逆序对的个数，即通过桶的思想将询问转换为线段树区间查询。

实现如下

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 500010;
ll sumv[maxn*4];
ll a[maxn],aa[maxn];
void pushup(ll id){
    sumv[id] = sumv[id << 1] + sumv[id << 1 | 1];
}
void build(ll id,ll l,ll r){
    if(l == r){
        sumv[id] = 0;
        return;
    }
    ll mid = (l + r) >> 1; 
    build(id << 1,l,mid);
    build(id << 1,mid+1,r);
    pushup(id);
}
ll query(ll id,ll l,ll r,ll x,ll y){
    if(x <= l && r <= y){
        return sumv[id];
    }
    ll mid = (l + r) >> 1;
    ll sum = 0;
    if(x <= mid){
        sum += query(id << 1,l,mid,x,y);
    }
    if(y > mid){
        sum += query(id << 1|1,mid+1,r,x,y);
    }
    return sum;
}
void update(ll id,ll l,ll r,ll x,ll v){
    if(l == r){
        sumv[id] += v;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid){
        update(id<<1,l,mid,x,v);
    }else{
        update(id<<1|1,mid+1,r,x,v);
    }
    pushup(id);
}
int main(){
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
        scanf("%lld",a+i);
        aa[i] = a[i];
    }
    sort(aa+1,aa+1+n);
    int m = unique(aa+1,aa+1+n) - aa - 1;
    for(int i=1;i<=n;i++){
        a[i] = lower_bound(aa+1,aa+1+n,a[i]) - aa;
    }
    ll ans = 0;
    build(1,1,500000);
    for(ll i=1;i<=n;i++){        
        if(a[n-i+1] == 1){
            update(1,1,n,a[n-i+1],1);
            continue;
        }
        ans += query(1,1,n,1,a[n-i+1]-1);
        update(1,1,n,a[n-i+1],1);
    }
    printf("%lld",ans);
    return 0;
}

背模板时学习到的:结构体线段树

在计蒜客学习的时候，我曾经背的线段树模板是非结构体，也就是线段树各种信息分成几个数组保存(什么maxv[] 啊，lazy [] 啊)，当然这种方法也可以，但是在这次完成模板题：线段树区间乘法，区间加法，区间求和同时被要求时，却感到满满的崩溃

首先是区间加的时候，对左右儿子维护的值加上lazy时，要考虑乘上权值(也就是左右儿子分别维护的元素的个数)，这个要在pushdown的时候多传进来两个参数l，r，还要自己算mid算子节点数。

然后是更恶心的区间乘，不仅要把乘法的lazy标记传下去，还要把加法的lazy标记加权，这个开始坑了我很久，一直找不出错误。

这个时候，我就很想有一个方法能够给出节点id，我就知道它维护的左右区间，各种lazy标记，还有本来的值。于是，题解里的结构体形式线段树就吸引了我。

struct node{
    long long l,r;
    long long lazyadd,lazymult,val;
}Seg[maxn * 5];

结构体形式的线段树本身没什么特色创新，无非只是把各种节点数据打包成了结构体放在一起，整体感更强了而已。但是在我实际应用中，却发现它真的很实用。在pushdown时，还是照常传一个id,但是在函数内部可以直接访问Seg[id<<1].l 和 Seg[id<<1].r 访问到子节点左右区间。这大大减少了代码的错误几率(什么mid没+1啊，什么求个数求成mid-l啊)，而且访问子节点非常直观，每个节点就是一个结构体，有它的各种属性。

代码上同以前的线段树没什么大的区别，只是在$build$函数和$pushdown$的一些细节上有些修改。

下面是代码:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const long long maxn = 150010;
ll fuckyouP;
struct node{
    long long l,r;
    ll lazyadd,lazymult,val;
}Seg[maxn * 5];
ll a[maxn];
void pushup(long long id){
    Seg[id].val = (Seg[id<<1].val + Seg[id<<1|1].val) % fuckyouP;
}
void pushdown(long long id){
    if(Seg[id].lazyadd || Seg[id].lazymult != 1){
    //prlong longf("lazyadd[%d]:%d\n",id,Seg[id].lazyadd);
        Seg[id << 1].val = Seg[id << 1].val * Seg[id].lazymult + Seg[id].lazyadd * (Seg[id<<1].r - Seg[id<<1].l + 1);
        Seg[id << 1].val %= fuckyouP;
        Seg[id << 1 | 1].val = Seg[id << 1 | 1].val * Seg[id].lazymult + Seg[id].lazyadd * (Seg[id<<1|1].r - Seg[id<<1|1].l + 1);
        Seg[id << 1 | 1].val %= fuckyouP;
        //prlong longf("pre---lazyadd[%d]:%d\n",id << 1,Seg[id << 1].lazyadd);
        Seg[id << 1].lazyadd = Seg[id << 1].lazyadd * Seg[id].lazymult + Seg[id].lazyadd;
        //prlong longf("post---lazyadd[%d]:%d\n",id << 1,Seg[id << 1].lazyadd);
        Seg[id << 1].lazyadd %= fuckyouP;
        Seg[id << 1].lazymult *= Seg[id].lazymult;
        Seg[id << 1].lazymult %= fuckyouP;
        Seg[id << 1 | 1].lazyadd = Seg[id << 1 | 1].lazyadd * Seg[id].lazymult + Seg[id].lazyadd;
        Seg[id << 1 | 1].lazyadd %= fuckyouP;
        Seg[id << 1 | 1].lazymult *= Seg[id].lazymult;
        Seg[id << 1 | 1].lazymult %= fuckyouP;
        Seg[id].lazyadd = 0;
        Seg[id].lazymult = 1;
    }
} 
void build(long long id,long long l,long long r){
    Seg[id].l = l,Seg[id].r = r;
    Seg[id].lazymult = 1;
    Seg[id].lazyadd = 0;
    if(l == r){
        Seg[id].val = a[l] % fuckyouP;
        
        //prlong longf("Seg[%d] = %lld\n",id,a[l]);
        return;
    }
    long long mid = l + r >> 1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    pushup(id);
}
void updateMult(long long id,long long l,long long r,long long x,long long y,long long v){
    if(x <= l && r <= y){
        Seg[id].val *= v;
        Seg[id].val %= fuckyouP;
        Seg[id].lazymult *= v;
        Seg[id].lazymult %= fuckyouP;
        Seg[id].lazyadd *= v;
        Seg[id].lazyadd %= fuckyouP;
        return;
    }
    pushdown(id);
    long long mid = l + r >> 1;
    if(x <= mid){
        updateMult(id << 1,l,mid,x,y,v);
    }
    if(y > mid){
        updateMult(id << 1 | 1,mid + 1,r,x,y,v);
    }
    pushup(id);
}
void updateAdd(long long id,long long l,long long r,long long x,long long y,long long v){
    if(x <= l && r <= y){
        Seg[id].val += v * (r - l + 1);
        //prlong longf("Seg[%d] += %d\n",id,v * (r - l + 1));
        Seg[id].val %= fuckyouP;
        Seg[id].lazyadd += v;
        //prlong longf("lazy[%d] += %d\n",id,v);
        Seg[id].lazyadd %= fuckyouP;
        return;
    }
    pushdown(id);
    long long mid = l + r >> 1;
    if(x <= mid){
        updateAdd(id << 1,l,mid,x,y,v);
    }
    if(y > mid){
        updateAdd(id << 1 | 1,mid + 1,r,x,y,v);
    }
    pushup(id);
}
ll query(long long id,long long l,long long r,long long x,long long y){
    if(x <= l && r <= y){
        //prlong longf("QUERY : Seg[%d] = %d\n",id,Seg[id].val);
        return Seg[id].val % fuckyouP;
    }
    //prlong longf("QUERY : pushdown %d\n",id);
    pushdown(id);
    long long mid = l + r >> 1;
    ll sum = 0;
    if(x <= mid){
        sum += query(id<<1,l,mid,x,y);
        sum %= fuckyouP;
    }
    if(y > mid){
        sum += query(id<<1|1,mid+1,r,x,y);
        sum %= fuckyouP;
    }
    return sum % fuckyouP;
}
long long n,m;
int main(){
    scanf("%lld%lld%lld",&n,&m,&fuckyouP);
    //cout << "p:" << p << endl;
    for(long long i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    build(1,1,n);
    for(long long i=1;i<=m;i++){
        long long act,x,y;
        scanf("%lld%lld%lld",&act,&x,&y);
        if(act == 1){
            long long k;
            scanf("%lld",&k);
            updateMult(1,1,n,x,y,k);
        }else if(act == 2){
            long long k;
            scanf("%lld",&k);
            updateAdd(1,1,n,x,y,k);
            //prlong longf("%d~%d +%d\n",x,y,k);
        }else{
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

最小环问题

这次的集训考了两次最小环问题，最小环问题我们以前练习得很少，也缺乏经验，这次自然两道题都是错的一塌糊涂，除了暴力骗分，没能做点什么。

但是却学习到了最小环的一些基本思想。那就是将最小环问题转换为最短路问题

最小环无非还是一条可行路径，只是以环中任意一个点看来，这条路径的起点都等于终点。那么我们确定起点过后，只要找到一条最小路，令终点等于起点，那么也就找到了最小环。

至于代码的实现，因为无论是优秀的$dijkstra$还是已死的$SPFA$(这次我最小环用SPFA过的,SPFA最小环又名CLZ最小，是由中国著名数学家，图论家ChenLizhe发明，以其优秀的复杂度和通俗易懂著名)，都有开一个数组名为 vis[] ，我们只需要从起点开始，但是不把起点的vis设为true，那么最后就一定可以得到由起点开始到起点的最短路

还有一种实现方法是Floyd，利用Floyd的三层循环维护的大信息量，完全可以够我们计算出最小环。

这里提供CLZ最小(SPFA)的实现，大神们能不能写下Dijkstra版本的发给我下...

void spfa(ll u,ll org){
    for(RG ll i=1;i<=n;i++){
        dis[i] = inf;
        disw[i] = inf;
        vis[i] = false;
    }
    queue<ll> q;
    dis[u] = 0;
    disw[u] = 0;
    vis[u] = true;
    q.push(u);
    bool first = true;
    while(!q.empty()){
        u = q.front();
        q.pop();
        vis[u] = false;
        for(ll i=p[u];~i;i=E[i].nxt){
            ll v = E[i].v;
            ll w = E[i].w;
            if(dis[u] + 1 < dis[v] && disw[u] + w < disw[v] && disw[u] + w > 0){
                dis[v] = dis[u] + 1;
                disw[v] = disw[u] + w;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
        if(first){
            vis[org] = false;
            dis[org] = inf;
            disw[org] = inf;
            first = false;
        }
    }
}

解释一下first是干嘛用的，由于最后结果是一个环，所以最后应该回到出发点，那么当第一次找的时候就要把出发点的vis设成false，这样后面走环回来时才能更新到出发点的dis

我早就会的:动态插入中位数问题

给定一个由 N 个元素组成的整数序列，现在有两种操作：

1 add a

在该序列的最后添加一个整数a，组成长度为N + 1的整数序列

2 mid 输出当前序列的中位数

这个问题方法的解释，我已经在我Day10的题解里说的非常清楚了，所以直接放出实现

namespace midProcess{
    struct node{
        int val,index;
    };
    
    bool operator > (const node &a,const node &b)
    {
        if(a.val == b.val){
            return a.index > b.index;
        }
        return a.val > b.val;
    }
    
    bool operator < (const node &a,const node &b)
    {
        if(a.val == b.val){
            return a.index < b.index;
        }
        return a.val < b.val;
    }
    
    priority_queue< node,vector<node>,greater<node> > smallHeap;
    priority_queue< node,vector<node>,less<node> > bigHeap;
    void clearAll(){
        while(!smallHeap.empty()) smallHeap.pop();
        while(!bigHeap.empty()) bigHeap.pop();
    }
    inline int myabs(int a,int b){
        if(a - b > 0) return a-b;
        return b-a;
    }
    inline void pushNum(int num,int index){
        if(smallHeap.empty()){
            smallHeap.push((node){num,index});
            return;
        }
        if(num < smallHeap.top().val){
            bigHeap.push((node){num,index});
        }else{
            smallHeap.push((node){num,index});
        }
    }
    inline pair<int,int> queryMid(){
        while(myabs(bigHeap.size(),smallHeap.size()) > 1){
            if(bigHeap.size() > smallHeap.size()){
                smallHeap.push(bigHeap.top());
                bigHeap.pop();
            }else{
                bigHeap.push(smallHeap.top());
                smallHeap.pop();
            }
        }
        if((smallHeap.size() + bigHeap.size()) & 1 == 1){
            if(smallHeap.size() > bigHeap.size()){
                return make_pair(smallHeap.top().val,smallHeap.top().index);
            }else{
                return make_pair(bigHeap.top().val,bigHeap.top().index);
            }
        }else{
            if(smallHeap.top().val < bigHeap.top().val){
                return make_pair(smallHeap.top().val,smallHeap.top().index);
            }else{
                return make_pair(bigHeap.top().val,bigHeap.top().index);
            }
        }
    }
};