国庆小结-526互联

国庆前几天把团体训练里的每日训练写完，加上每天一场edu，后几天刷的洛谷数据结构。

个人感觉比较有意义的题目：

C. Not Equal on a Segment

题目大意：给出一个长度为n的数列，然后给出m次询问，每次询问的格式是l,r,x，要求我们输出任意一个在区间[l,r]内值不等于x的下标

这题目好像是可以直接递推的写，只需要记录连续相同的数第一次出现位置，依次递推。

但是我用的ST表+二分写的。

实现思路：对于每一个查询，用ST表查出该区间最大值与最小值，如果最大值和最小值相等并且等于x，输出-1；

否则，首先预处理出每个值的所在下标，我用的set存每个值的下标，然后二分查询两个最值中不等于x的值在[l,r]区间内的下标。

代码：

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#define endl '\n'

using namespace std;

const int N = 2e5+10 , M = 1e6+10 ;

int n,m;
int fi[N][20],fx[N][20],lg[N];

set<int> s[M];

void init() {
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int j=1;j<=18;j++) {
        for(int i=1;i+(1<<j)-1<=n;i++) {
            fi[i][j]=min(fi[i][j-1],fi[i+(1<<(j-1))][j-1]);
            fx[i][j]=max(fx[i][j-1],fx[i+(1<<(j-1))][j-1]);
        }
    }
}

int query_min(int l,int r) {
    int k = lg[r-l+1];
    return min(fi[l][k],fi[r-(1<<k)+1][k]);
}

int query_max(int l,int r) {
    int k = lg[r-l+1];
    return max(fx[l][k],fx[r-(1<<k)+1][k]);
}

void solve() {
    cin >> n >> m;
    memset(fi , M , sizeof fi);
    for(int i=1;i<=n;i++) {
        int x;
        cin >> x;
        fi[i][0]=x , fx[i][0]=x;
        s[x].insert(i);
    }
    init();
    while(m--) {
        int l,r,x;
        cin >> l >> r >> x;
        int a = query_min(l,r) , b = query_max(l,r);
        if(a==b && b==x) cout << -1 << endl;
        else {
            int w;
            if(a==x) w=b;
            else w=a;
            int t = *s[w].lower_bound(l);
            cout << t << endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}

C：Foe Pairs

题意：给定一些线段，请计算有多少个区间满足没有一条线段被完整包含。

思考：对于每个左端点枚举从该点往后走，最远能走到哪，首先初始化所有点能到的最远距离f[i]=n

题解：先处理单点再前缀扫一遍：令f[i]表示 i 位置往左往右走到最远的地方是哪，对于所有区间[l,r]，左端点在 l 的线段f[l]=min(f[l],r-1);最后作一个后缀最小值f[i]=min(f[i],f[i+1]),表示每个点能走到的最远距离即可。

代码：

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define endl '\n'
#define int long long
using namespace std;

const int N = 3e5+10 , M = 1e6+10;

int n,m;
int k[N],f[N];

void solve() {
    cin >> n >> m;
    map<int , int> mp;
    for(int i=1;i<=n;i++) {
        cin >> k[i];
        mp[k[i]]=i;
        f[i]=n;
    }
    for(int i=1;i<=m;i++) {
        int l,r;
        cin >> l >> r;
        l = mp[l] , r = mp[r];
        if(l>r) swap(l,r);
        f[l]=min(f[l],r-1);
    }
    for(int i=n-1;i>=1;i--) f[i]=min(f[i],f[i+1]);
    int ans=0;
    for(int i=1;i<=n;i++) ans+=f[i]-i+1;
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}

C. Nested Segments

题意：在一条直线上有 n 条线段。有些线段的两端不重合。求每条线段包含的线段数。

思考：题意挺简单的，先开始感觉是贪心，结果一写发现不对，不是贪心，根本贪不了；但是线段覆盖这种问题想半天我也没想到有啥写法，看题解发现树状数组居然能写（可能是我脑子宕机了，真没想到）

题解：我们将线段按照左端点从大到小排序，然后树状数组对每条线段的右端点进行修改和查询（数据范围很大，要先离散化）。这样我们就能保证，在查询点之前的线段的左右端点一定在当前线段左右端点之间。

代码：

const int N = 4e5+10 , M = 1e6+10 ;

int n , cnt=1;
int tr[N] , ans[N];

struct node{
    int x,y,id;
}k[N];

bool cmp1(node a,node b) {
    if(a.x == b.x) return a.y < b.y;
    return a.x > b.x;
}

bool cmp2(node a ,node b) {
    return a.id < b.id;
}

int lowbit(int x) {
    return x & -x;
}

void add(int x) {
    for(int i=x;i<=cnt;i+=lowbit(i)) tr[i]++;
}

int query(int x) {
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

void solve() {
    cin >> n;
    map<int , int> mp;
    for(int i=1;i<=n;i++) {
        cin >> k[i].x >> k[i].y;
        mp[k[i].x]=1 , mp[k[i].y]=1 , k[i].id=i;
    }
    for(auto & [a,b] : mp) mp[a]=cnt , cnt++;
    sort(k+1,k+n+1,cmp1);
    for(int i=1;i<=n;i++) {
        int y = mp[k[i].y];
        ans[k[i].id]=query(y);
        add(y);
    }
    sort(k+1,k+n+1,cmp2);
    for(int i=1;i<=n;i++) cout << ans[i] << endl;
}

洛谷复习的和刷的一点数据结构，这里都是一些简单的数据结构，并查集，ST表，树状数组啥的，后续会继续刷线段树的题。

然后10月4日下午，令人悲伤的事情发生了?，突然高烧至39度，头昏头痛，所以最后两天没干啥，在寝室呆了两天休息。