题解 | # 贤断术 #

羊开茗，快来学习贤断术

题目一：https://www.luogu.com.cn/problem/P10589

使用权值线段树（因为我一开始用普通线段树超时了）

对每一个位置 $i$ ，求区间 $[1,i-1]$ 和 $[i+1,n]$ 中有多少个比 $a[i]$ 大的数和比 $a[i]$ 小的数

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 200000 + 100;

struct Node{
    int l, r;
    int cnt;
}tr[4 * N];

int n, a[N];

void build(int u, int l, int r){
    if(l == r){
        tr[u] = {l, r, 0};
        return ;
    }
    else{
        tr[u] = {l, r, 0};
        int mid = (tr[u].l + tr[u].r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
}

void modify(int u, int x){
    if(tr[u].l == tr[u].r){
        tr[u].cnt ++;
        return ;
    }
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) modify(u << 1, x);
        else modify(u << 1 | 1, x);
        tr[u].cnt = (tr[u << 1].cnt + tr[u << 1 | 1].cnt);
    }
}

int query(int u, int l, int r){
    if(l > r) return 0;
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].cnt;
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        int sum = 0;
        if(l <= mid) sum += query(u << 1, l, r);
        if(r > mid) sum += query(u << 1 | 1, l, r);
        return sum;
    } 
}
void solve(){
    
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    build(1, 1, n);
    vector<int> pre_max(n + 10), pre_min(n + 10);
    for(int i = 1; i <= n; i ++){
        pre_max[i] = query(1, a[i] + 1, n);
        pre_min[i] = query(1, 1, a[i] - 1);
        modify(1, a[i]);
    }
    build(1, 1, n);
    vector<int> suf_max(n + 10), suf_min(n + 10);
    for(int i = n; i >= 1; i --){
        suf_max[i] = query(1, a[i] + 1, n);
        suf_min[i] = query(1, 1, a[i] - 1);
        modify(1, a[i]);
    }
    int ans1 = 0, ans2 = 0;
    for(int i = 1; i <= n; i ++){
        ans1 += pre_max[i] * suf_max[i];
        ans2 += pre_min[i] * suf_min[i];
    }
    cout << ans1 << " " << ans2 << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目二：https://www.luogu.com.cn/problem/P3368

题目三：https://www.luogu.com.cn/problem/P3372

模板，不贴代码了

题目四：https://www.luogu.com.cn/problem/P10497

倒着枚举：样例 $a[2-n]= \{1,2,1,0\}$ ，

对于 $a[n]=0$ ，说明前面有 $0$ 头牛比第 $n$ 头的牛的身高低，所以第 $n$ 头的牛的身高是第 $1$ 小的，即 $1$

对于 $a[n - 1]=1$ ，说明前面有 $1$ 头牛比第 $n-1$ 头的牛的身高低，所以第 $n-1$ 头的牛的身高是第 $2$ 小的，应该为 $2$ 么？不是的，因为前面的 $1$ 已经被用了，所以在目前的所有可以选择的身高： $[-1,2,3,4,5]$ 里面，第 $2$ 小的是 $3$ .

同样，对于 $a[n - 2]=2$ ，那么第 $n-2$ 头的牛的身高是第 $3$ 小的，目前所有可以选择的身高为 $[-1,2,-1,4,5]$ ，所以身高为 $5$

依旧可以使用权值线段树，从后枚举答案以及进行删除操作

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 8000 + 100;

int n, a[N];

struct Node{
    int l, r;
    int cnt;
}tr[4 * N];


void build(int u, int l, int r){
    if(l == r){
        tr[u] = {l, r, 0};
        return ;
    }
    else{
        tr[u] = {l, r, 0};
        int mid = (tr[u].l + tr[u].r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
}

void modify(int u, int x, int v){
    if(tr[u].l == tr[u].r){
        tr[u].cnt += v;
        return ;
    }
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
    }
}

int query(int u, int x){
    if(tr[u].l == tr[u].r) return tr[u].l;
    else{
        if(tr[u << 1].cnt >= x) return query(u << 1, x);
        else return query(u << 1 | 1, x - tr[u << 1].cnt);
    }
}
void solve(){

    cin >> n;
    build(1, 1, n);
    for(int i = 1; i <= n; i ++) modify(1, i, 1);
    for(int i = 2; i <= n; i ++) cin >> a[i];
    vector<int> ans(n + 10);
    for(int i = n; i >= 1; i --){
        ans[i] = query(1, a[i] + 1);
        modify(1, ans[i], -1);
    }
    for(int i = 1; i <= n; i ++) cout << ans[i] << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目五：https://www.luogu.com.cn/problem/SP1716

求最大字段和，太经典的题目了

$query$ 函数中必须返回 $Node$ ，因为区间最大字段和的答案不是孤立的数字，而是需要用子区间的 $sum,l\_max,r\_max$ 计算出来，而如果返回 $int$ ，只能存一个数，存不下这些计算必须的辅助信息。

如果查询区间的有边界小于等于 $mid$ ，说明查询区间在 $tr[u]$ 的左子树；如果查询区间的左边界大于 $mid$ ，说明查询区间在 $tr[u]$ 的右子树，直接返回即可

if(r <= mid) return query(u << 1, l, r);
if(l > mid) return query(u << 1 | 1, l, r);

如果都不是的话，说明查询区间横跨左右子树，所以得新建一个 $Node\ res$

Node left = query(u << 1, l, r);
Node right = query(u << 1 | 1, l, r);
Node res;

总代码：

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

#define int long long
#define endl '\n'

const int N = 500000 + 100;

int n, m, a[N];

struct Node{
    int l, r;
    int sum, lmax, rmax, tmax;
}tr[4 * N];


void push_up(int u){
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].lmax = max(tr[u << 1].lmax, tr[u << 1].sum + tr[u << 1 | 1].lmax);
    tr[u].rmax = max(tr[u << 1 | 1].rmax, tr[u << 1 | 1].sum + tr[u << 1].rmax);
    tr[u].tmax = max({tr[u << 1].tmax, tr[u << 1 | 1].tmax, tr[u << 1].rmax + tr[u << 1 | 1].lmax});
}

void build(int u, int l, int r){
    if(l == r){
        tr[u] = {l, l, a[l], a[l], a[l], a[l]};
        return ;
    }
    else{
        tr[u] = {l, r, 0, 0, 0, 0};
        int mid = (tr[u].l + tr[u].r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
}

void modify(int u, int pos, int x){
    if(tr[u].l == tr[u].r){
        tr[u].sum = x;
        tr[u].lmax = x;
        tr[u].rmax = x;
        tr[u].tmax = x;
        return ;
    }
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(pos <= mid) modify(u << 1, pos, x);
        else modify(u << 1 | 1, pos, x);
        push_up(u);
    }
}

Node query(int u, int l, int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u];
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l > mid) return query(u << 1 | 1, l, r);
        if(r <= mid) return query(u << 1, l, r);
        Node left = query(u << 1, l, r);
        Node right = query(u << 1 | 1, l, r);
        Node res;
        res.sum = left.sum + right.sum;
        res.lmax = max(left.lmax, left.sum + right.lmax);
        res.rmax = max(right.rmax, right.sum + left.rmax);
        res.tmax = max({left.tmax, right.tmax, left.rmax + right.lmax});
        return res;
    }
}

signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    build(1, 1, n);
    while(m --){
        int op; cin >> op;
        if(op == 1){
            int x, y; cin >> x >> y;
            if(x > y) swap(x, y);
            cout << query(1, x, y).tmax << endl;
        }
        else{
            int x, y; cin >> x >> y;
            modify(1, x, y);
        }
    }
    return 0;
}

题目六：https://www.luogu.com.cn/problem/P10463

求带修改操作的区间 $gcd$ ，太经典的题目了

因为 $gcd(x, y,z)=gcd(x,y-x,z-y)$ ，所以维护普通的区间 $gcd$

区间修改操作，维护差分进行两次单点修改

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

const int N = 500000 + 100;
int n, m, a[N];

struct Node{
    int l, r;
    int sum, Gcd;
}tr[4 * N];


int gcd(int a, int b){
    if(!b) return a;
    else return gcd(b, a % b);
}

void push_up(int u){
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].Gcd = gcd(tr[u << 1].Gcd, tr[u << 1 | 1].Gcd);
}

void build(int u, int l, int r){
    if(l == r){
        tr[u] = {l, r, a[l] - a[l - 1], a[l] - a[l - 1]};
        return ;
    }
    else{
        tr[u] = {l, r, 0, 0};
        int mid = (tr[u].l + tr[u].r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
}

void modify(int u, int pos, int x){
    if(tr[u].l == tr[u].r){
        tr[u].sum += x;
        tr[u].Gcd += x;
        return ;
    }
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(pos <= mid) modify(u << 1, pos, x);
        else modify(u << 1 | 1, pos, x);
        push_up(u);
    }
}

int query_sum(int u, int l, int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        int sum = 0;
        if(l <= mid) sum += query_sum(u << 1, l, r);
        if(r > mid) sum += query_sum(u << 1 | 1, l, r);
        return sum;
    }
}

int query_gcd(int u, int l, int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].Gcd;
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        int g = 0;
        if(l <= mid) g = gcd(query_gcd(u << 1, l, r), g);
        if(r > mid) g = gcd(query_gcd(u << 1 | 1, l, r), g);
        return g;
    }
}

void solve(){

    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    build(1, 1, n);
    while(m --){
        char op; cin >> op; 
        if(op == 'Q'){
            int l, r; cin >> l >> r;
            int x = query_sum(1, 1, l);
            int y = query_gcd(1, l + 1, r);
            cout << abs(gcd(x, y)) << endl;
        }
        else{
            int l, r, x; cin >> l >> r >> x;
            modify(1, l, x);
            if(r + 1 <= n) modify(1, r + 1, -x);
        }
    }
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目七：https://www.luogu.com.cn/problem/P5490

扫描线求并面积，相当于线段树扫描线的经典模板题目

扫描线：试想，如果我们用一条竖直直线从左到右扫过整个过程，那么直线上被并集图形覆盖的长度只会在每个矩形的左右边界发生变化。换言之，整个并集图形可以被分成 $2 \times N - 1$ 段，每一段在直线上覆盖的长度（记为 $L$ ）是固定的，因此该段的面积就是 $L \times$ 该段的宽度，各段面积之和即为所求。这条直线就被称为扫描线，这种解题思路被称为扫描线法。

$segment$ 结构体代表一条扫描线，将每个矩形的左右两条竖边抽象为线段

$x$ ：竖边所在的横坐标

$y_{1},y_{2}$ ：表示竖边的上下端点

$k$ ：权值，左边的边标记为 $+1$ （表示进入矩形，覆盖次数 $+1$ ），右边的边标记为 $-1$ （表示离开矩形，覆盖次数 $-1$ ）。

struct segment{
    int x, y1, y2;
    int k;
}seg[N];

$Node$ 结构体，线段树的节点

$l,r$ ：该节点代表的区间下标，注意是离散化的下标

$cnt$ ：该区间被覆盖的次数，懒标记不下传

$len$ ：该区间内被覆盖的总长度

叶子节点 $tr[u]$ 表示的线段树 $Node$ 区间 $[tr[u].l,tr[u].r]$ 维护离散化后的区间 $[v[tr[u].l], v[tr[u].r+1]]$

struct Node{
    int l, r;
    int cnt;
    int len;
}tr[4 * N];

用于离散化纵坐标

vector<int> v;

将所有矩形的线段按照 $x$ 从小到大排序，按照扫描线从左往右扫描整个平面

bool cmp(segment a, segment b){
    return a.x < b.x;
}

二分离散化查找离散化后的数组下标

int find(int y){
    return lower_bound(v.begin(), v.end(), y) - v.begin();
}

在 $push\_up$ 函数中，如果 $tr[u].cnt\ne 0$ ，说明该区间被覆盖，那么该区间的 $tr[u].len$ 就设置为 $v[tr[u].r+1] - v[tr[u].l]$

如果 $tr[u].cnt = 0$ ，在如果 $tr[u]$ 不是叶子节点，即 $tr[u].l \ne tr[u].r$ ，则 $tr[u].len$ 等于左右两个子区间的 $len$

如果 $tr[u].cnt = 0$ 并且也是叶子节点，则区间长度设置为 $0$

void push_up(int u){
    if(tr[u].cnt) tr[u].len = (v[tr[u].r + 1] - v[tr[u].l]);
    else if(tr[u].l != tr[u].r) tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    else tr[u].len = 0;
}

在 $modify$ 函数中， $modify$ 函数的作用是修改区间的 $cnt$ ，从而通过 $push\_up$ 影响区间的 $len$

在判断语句 $if(l \leq tr[u].l \ \&\&\ tr[u].r \leq r)$ 中，多了一步 $push\_up$ 操作当前 $Node$ 的 $cnt$ 有变化，则也会影响当前 $Node$ 的l $len$ ，所以也会 $push\_up$

void modify(int u, int l, int r, int k){
    if(l <= tr[u].l && tr[u].r <= r){
        tr[u].cnt += k;
        push_up(u);
        return ;
    }
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) modify(u << 1, l, r, k);
        if(r > mid) modify(u << 1 | 1, l, r, k);
        push_up(u);
    }
}

离散化后的纵坐标有 $v.size()$ 个，那么有 $v.size()-1$ 个区间，因为下标从 $0$ 开始，所以最后一个区间范围是 $[v[v.size()-2],v[v.size()-1]]$ ，所以线段树维护区间范围是 $[0,v.size()-2]$

build(1, 0, v.size() - 2);

累加答案时，直接调用这个区间的长度 $tr[1].len$

注意 $find(seg[i].y_{2})$ 要减去 $1$ ，因为 $find(seg[i].y_{2})$ 包含的是下一个区间，所以得减去 $1$

for(int i = 0; i < idx; i ++){
    if(i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
    modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
}

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 200000 + 100;

struct segment{
    int x, y1, y2, k;
}seg[N];

struct Node{
    int l, r;
    int cnt, len;
}tr[4 * N];

vector<int> v;
int find(int y){
    return lower_bound(v.begin(), v.end(), y) - v.begin();
}

bool cmp(segment a, segment b){
    return a.x < b.x;
}



void push_up(int u){
    if(tr[u].cnt) tr[u].len = v[tr[u].r + 1] - v[tr[u].l];
    else if(tr[u].l != tr[u].r) tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    else tr[u].len = 0;
}

void build(int u, int l, int r){
    if(l == r){
        tr[u] = {l, r, 0, 0};
        return ;
    }
    else{
        tr[u] = {l, r, 0, 0};
        int mid = (tr[u].l + tr[u].r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
}

void modify(int u, int l, int r, int k){
    if(l <= tr[u].l && tr[u].r <= r){
        tr[u].cnt += k;
        push_up(u);
        return ;
    }
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) modify(u << 1, l, r, k);
        if(r > mid) modify(u << 1 | 1, l, r, k);
        push_up(u);
    }
}


void solve(){

    int n; cin >> n;
    int idx = 0;
    for(int i = 0; i < n; i ++){
        int x1, y1, x2, y2; 
        cin >> x1 >> y1 >> x2 >> y2;
        seg[idx ++] = {x1, y1, y2, 1};
        seg[idx ++] = {x2, y1, y2, -1};
        v.push_back(y1), v.push_back(y2);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    build(1, 0, (int)v.size() - 2);
    sort(seg, seg + idx, cmp);

    int res = 0;
    for(int i = 0; i < idx; i ++){
        if(i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
        modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
    }
    cout << res << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

后面再更新