线段树 离散化 E. Infinite Inversions E. Physical Education Lessons

时间：2024-10-23 13:34:44

题目一：E. Infinite Inversions

这个题目没什么思维量，还比较简单，就是离散化要加上每一个值的后面一个值，然后每一个值放进去的不是1 ，而是这个值与下一个点的差值。

因为这个数代表了一堆数，然后每一次的找到了的逆序对都要乘以这个num。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <string>

#include <iostream>

#include <map>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 4e5 + ;

typedef long long ll;

int num[maxn], a[maxn], b[maxn];

pair<ll, ll>ex[maxn];

struct node {

    int l, r;

    int num;

}tree[ * maxn];

 

 

void build(int id, int l, int r) {

    tree[id].l = l;

    tree[id].r = r;

    if (l == r) {

        tree[id].num = ;

        return;

    }

    int mid = (l + r) >> ;

    build(id << , l, mid);

    build(id <<  | , mid + , r);

}

 

int query(int id, int x, int y) {

    int l = tree[id].l;

    int r = tree[id].r;

    if (x <= l && y >= r) {

        return tree[id].num;

    }

    int ans = ;

    int mid = (l + r) >> ;

    if (x <= mid) ans += query(id << , x, y);

    if (y > mid) ans += query(id <<  | , x, y);

    return ans;

}

 

void push_up(int id) {

    tree[id].num =tree[id << ].num+tree[id <<  | ].num;

}

 

void update(int id, int x, int val) {

    int l = tree[id].l;

    int r = tree[id].r;

    if (l == r) {

        //printf("id=%d x=%d val=%d\n", id, x, val);

        tree[id].num = val;

        return;

    }

    int mid = (l + r) >> ;

    if (x <= mid) update(id << , x, val);

    else update(id <<  | , x, val);

    push_up(id);

}

 

int main() {

    int n, tot = ;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) {

        int u, v;

        scanf("%d%d", &u, &v);

        ex[i] = make_pair(u, v);

        a[tot++] = u, a[tot++] = v;

        a[tot++] = u + , a[tot++] = v + ;

    }

    sort(a, a + tot);

    int len = unique(a, a + tot) - a;

    //printf("len=%d\n", len);

    num[len - ] = ;

    for (int i = ; i < len - ; i++) {

        num[i] = a[i + ] - a[i];

        //printf("num[%d]=%d a[%d]=%d\n", i, num[i], i, a[i]);

    }

    memcpy(b, a, sizeof(a));

    for(int i=;i<=n;i++)

    {

        ex[i].first = lower_bound(a, a + len, ex[i].first) - a;

        ex[i].second = lower_bound(a, a + len, ex[i].second) - a;

        //printf("ex[%d] %lld %lld\n", i, ex[i].first, ex[i].second);

    }

    for (int i = ; i <= n; i++) swap(a[ex[i].first], a[ex[i].second]), swap(num[ex[i].first], num[ex[i].second]);

    ll ans = ;

    build(, , len);

    for(int i=;i<len;i++)

    {

        int l = lower_bound(b, b + len, a[i]) - b + ;

        //printf("l=%d\n", l);

        ans += query(, l, len) * 1ll * num[i];

        update(, l, num[i]);

        //printf("ans=%lld\n", ans);

    }

    printf("%lld\n", ans);

    return ;

}

离散化+线段树

今天20190809来补一下这个题目的树状数组，一直都没有学过树状数组，今天浅显的学习了一下，学习网站https://www.cnblogs.com/xenny/p/9739600.html

这个讲的还是很详细也很容易理解。

这个还是照着上面的思路，只是把线段树换成树状数组。

今天感觉自己傻了，这个树状数组容易写，但是下面的这个离散化写搓了，这个num数组应该记录的是这个数带这五个数的后面一位有多少个

而不可以是这个数和这个数的前面一位之间有多少个，因为这个比这个数小的肯定比大于这个数的数小，所以肯定是可以构成逆序对的。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <string>

#include <algorithm>

#include <iostream>

#include <map>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 4e5 + ;

int n;

ll c[maxn]; //对应原数组和树状数组

int lowbit(int x) {

    return x & (-x);

}

void updata(int i, ll k) {    //在i位置加上k

    while (i <= n) {

        c[i] += k;

        i += lowbit(i);

    }

}

ll getsum(int i) {        //求A[1 - i]的和

    ll res = ;

    while (i > ) {

        res += c[i];

        i -= lowbit(i);

    }

    return res;

}

ll num[maxn];

ll b[maxn], a[maxn];

struct node {

    int l, r;

    node(int l = , int r = ) :l(l), r(r) {}

}ex[maxn];

int main() {

    int m, tot = ;

    scanf("%d", &m);

    for (int i = ; i <= m; i++) {

        int l, r;

        scanf("%d%d", &l, &r);

        ex[i] = node(l, r);

        b[++tot] = l; b[++tot] = l + ;

        b[++tot] = r; b[++tot] = r + ;

    }

    sort(b + , b +  + tot);

    n = unique(b + , b +  + tot) - b - ;

    num[n] = ;

    for (int i = ; i < n; i++) {

        num[i] = b[i + ] - b[i];

    }

    memcpy(a, b, sizeof(b));

    for (int i = ; i <= m; i++) {

        ex[i].l = lower_bound(b + , b +  + n, ex[i].l) - b;

        ex[i].r = lower_bound(b + , b +  + n, ex[i].r) - b;

    }

    for (int i = ; i <= m; i++) {

        swap(a[ex[i].l], a[ex[i].r]), swap(num[ex[i].l], num[ex[i].r]);

    }

    ll ans = ;

    for (int i = ; i <= n; i++) {

        int l = lower_bound(b + , b +  + n, a[i]) - b;

        ll res = getsum(n) - getsum(l);

        ans += res * num[i];

        updata(l, num[i]);

    }

    printf("%lld\n", ans);

    return ;

}

树状数组

题目二：E. Physical Education Lessons

这个空间开的特别变态，空间要开的很大，而且这个空间给的也不是很多，没什么思维量，比较简单。

开始在第17发 re到我怀疑我写搓了，然后就是第一发mle。。。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <string>

#include <iostream>

#include <map>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn1 = 1e7 + 5e6 + ;

const int maxn = 3e5 + ;

typedef long long ll;

int a[maxn * ], num[maxn1];

struct edge {

    int u, v, opt;

    edge(int u = , int v = , int opt = ) :u(u), v(v), opt(opt) {}

}order[maxn * ];

struct node {

    int lazy;

    int sum, num;

}tree[maxn1];

 

void push_up(int id) {

    tree[id].sum = tree[id << ].sum + tree[id <<  | ].sum;

    tree[id].num = tree[id << ].num + tree[id <<  | ].num;

}

 

void build(int id, int l, int r) {

    tree[id].lazy = -;

    if (l == r) {

        tree[id].sum = num[l];

        tree[id].num = num[l];

        return;

    }

    int mid = (l + r) >> ;

    build(id << , l, mid);

    build(id <<  | , mid + , r);

    push_up(id);

}

 

void push_down(int id) {

    if (tree[id].lazy != -) {

        tree[id << ].sum = tree[id << ].num*tree[id].lazy;

        tree[id <<  | ].sum = tree[id <<  | ].num*tree[id].lazy;

        tree[id << ].lazy = tree[id].lazy;

        tree[id <<  | ].lazy = tree[id].lazy;

        tree[id].lazy = -;

    }

}

 

void update(int id,int l,int r, int x, int y, int k) {

    push_down(id);

    if (x <= l && y >= r) {

        tree[id].lazy = k;

        tree[id].sum = tree[id].num*k;

        return;

    }

    int mid = (l + r) >> ;

    if (x <= mid) update(id << , l, mid, x, y, k);

    if (y > mid) update(id <<  | , mid + , r, x, y, k);

    push_up(id);

}

 

int main() {

    int n, m, tot = ;

    scanf("%d%d", &n, &m);

    a[] = ;

    for (int i = ; i <= m; i++) {

        int u, v, k;

        scanf("%d%d%d", &u, &v, &k);

        order[i] = edge(u, v, k);

        a[tot++] = u, a[tot++] = u + ;

        a[tot++] = v, a[tot++] = v + ;

    }

    sort(a, a + tot);

    int len = unique(a, a + tot) - a;

    for (int i = ; i <= m; i++) {

        order[i].u = lower_bound(a, a + len, order[i].u) - a + ;

        order[i].v = lower_bound(a, a + len, order[i].v) - a + ;

    }

    num[len] = n - a[len - ] + ;

    for (int i = ; i < len - ; i++) {

        num[i + ] = a[i + ] - a[i];

        //printf("num[%d]=%d\n", i + 1, num[i + 1]);

    }

    //for (int i = 1; i <= len; i++) printf("i=%d %d\n",i, num[i]);

    build(, , len);

    //printf("len=%d\n", len);

    for (int i = ; i <= m; i++) {

        int l = order[i].u;

        int r = order[i].v;

        int k = order[i].opt;

        //printf("l=%d r=%d\n", l, r);

        if (l > r) swap(l, r);

        update(,,len, l, r, k - );

        ll ans = tree[].sum;

        printf("%lld\n", ans);

    }

    return ;

}

离散化+线段树

相关文章