[数据结构与算法]数据结构提高

PPT 数据结构

树状数组

HDU4911

给你一串数字，然后给你最多进行k次交换（只能交换相邻的）问交换后的最小逆序数是多少。

我们求出逆序对后 逆序对数-k 就是答案

注意：开ll，和0取max

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 50;
int n;
ll k;
int a[MAXN], tr[MAXN];

struct node{
    int val, id;
    bool operator<(const node &a)
    {
        if(val == a.val) return id < a.id;
        return val < a.val;
    }
}N[MAXN];

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

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

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

int main()
{
    while(cin >> n >> k)
    {
        memset(tr, 0, sizeof(tr));
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            N[i].val = a[i];
            N[i].id = i;
        }
        sort(N + 1, N + n + 1);

        ll ans = 0;
        for(int i = 1; i <= n; i++)
        {
            add(N[i].id, 1);
            ans += (ll)(i - getsum(N[i].id));
        }
        printf("%lld\n", max(ans - k, (ll)0));
    }
    return 0;
}

高位树状数组

HDU3584

高位树状数组维护差分

三维的空间中有N个元素，初始时每个空间元素均为0。
更新操作是0变1，1变0，是一个立方体型区域内的所有元素都更新。
然后查询是问某个点的元素是0还是1

$n?n?n$的矩阵，值为0 或者1 ，“1”操作改变(x1,y1,z1)到(x2,y2,z2)内的所有点，“0”操作问(x,y,z)的值，也就是统计改变的次数。

同一维，二维一样，定义一个数组a，$a[i][j][k]$表示(i,j,k)到(n,n,n)的矩形中每个点都改$a[i][j][k]$次，对于(x1,y1,z1)到(x2,y2,z2)的矩形改变1次，可以转化为

$a[x1][y1][z1]+=1$，还要把多加的删去（如a(x1,y1,z1+1) += -1 等），最后保证仅对(x1,y1,z1)到(x2,y2,z2)改变

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int c[110][110][110] ;
int lowbit(int x)
{
    return x & -x ;
}
int add(int i,int j,int k,int n,int d)
{
    int x , y , z ;
    for(x = i ; x <= n ; x += lowbit(x))
        for(y = j ; y <= n ; y += lowbit(y))
            for(z = k ; z <= n ; z += lowbit(z))
                c[x][y][z] += d ;
}
int sum(int i,int j,int k)
{
    int a = 0 , x , y , z ;
    for(x = i ; x > 0 ; x -= lowbit(x))
        for(y = j ; y > 0 ; y -= lowbit(y))
            for(z = k ; z > 0 ; z -= lowbit(z))
                a += c[x][y][z];
    return a ;
}
int main()
{
    int k , n , m , x , y , z ;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        memset(c,0,sizeof(c));
        while(m--)
        {
            scanf("%d %d %d %d", &k, &x, &y, &z);
            if(k == 0)
            {
                printf("%d\n", sum(x,y,z)%2);
            }
            else
            {
                int x1 , y1 , z1 ;
                scanf("%d %d %d", &x1, &y1, &z1);
                add(x,y,z,n,1);
                add(x1+1,y,z,n,-1);
                add(x,y1+1,z,n,-1);
                add(x,y,z1+1,n,-1);
                add(x1+1,y1+1,z,n,1);
                add(x1+1,y,z1+1,n,1);
                add(x,y1+1,z1+1,n,1);
                add(x1+1,y1+1,z1+1,n,-1);
            }
        }
    }
    return 0;
}

RMQ

Problem - 5289 (hdu.edu.cn)

题意：给你n个数，然后连续的，且这个区间内最大值减去最小值的差小于k的话，就可以算作一队。问你一共有多少种分队的方法。

RMQ预处理区间最值
暴力枚举左端点位置，然后二分枚举右端点
RMQ区间计算极差就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 50, N = 20;
int T, n, k;
int a[MAXN], maxx[MAXN][N], minn[MAXN][N];

void init()
{
    for(int j = 0; j < N; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            if(j == 0) {
                maxx[i][j] = a[i];
                minn[i][j] = a[i];
            }
            else {
                maxx[i][j] = max(maxx[i][j - 1], maxx[i + (1 << (j - 1))][j - 1]);
                minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
}

int querymax(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);
    int ans = max(maxx[l][k], maxx[r - (1 << k) + 1][k]);
    return ans;
}

int querymin(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);
    int ans = min(minn[l][k], minn[r - (1 << k) + 1][k]);
    return ans;
}

bool check(int l, int r)
{
    int mx = querymax(l, r), mi = querymin(l, r);
    //printf("l = %d r = %d mx = %d mi = %d\n", l, r, mx, mi);
    if(mx - mi < k) return true;
    else return false;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        init();
        ll ans = 0;
        for(int i = 1; i <= n; i++)
        {
            int l = i, r = n;
            while(l <= r)
            {
                int mid = (l + r) >> 1;
                if(check(i, mid)) l = mid + 1;
                else r = mid - 1;
            }
            ans += (r - i + 1);
            //printf("%lld\n", ans);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

HDU5726

给你n个数，Q次询问，问你(l,r)区间的gcd是多少，然后再问你整个序列中，有多少子串的gcd和询问的GCD是相同的。

RMQ预处理区间gcd
暴力枚举区间左端点，二分“新的”右端点
RMQ查询从左端点到右端点的gcd

LCA

求公共最近祖先的算法（设询问次数为q）

暴力（实际做题不可行）：对于每个询问，遍历所有的点，时间复杂度为O(n*q)。

Tarjan（离线）算法： 在一次遍历中把所有询问一次性解决，预处理时间复杂度O(nlogn),每次查询时间复杂度O(1)，总时间复杂度是O(nlogn+q)。

倍增算法：利用二分两个节点同时往上走，直到相遇，预处理时间复杂度O(nlogn)，每次查询时间复杂度O(logn)，总时间复杂度O(nlogn+qlogn)。

RMQ算法。

Codeforces Gym 100015C

Attachments - 2011-2012 Stanford Local Contest, 8 October, 2011 - Codeforces

线段树

Problem - E - Codeforces

题意：你可以从第$i$个城市买的从$i$到$[i+1,a[i]]$的车票，现在$p[i][j]$表示从$i$到$j$的最小车票花费，求$\Sigma p[i][j]$

思路：

$dp[i]={\sum }_{j=i+1}^n[i][j]$

显然，$i$站只需要一步就能到$[i+1,a[i]]$这个范围内的站，

至于$[a[i]+1,n]$之间的值，从后往前更新，它的下一步必然是最大的$i?>tmp$，保证$a[tmp]$最大。

对于所有的点至少走一步$n?i$，再走到最大的$tmp$继承了$dp[tmp]$，此时多走的部分为$a[i]?tmp$，此时只需要走一步。

$dp[i]=dp[tmp]+(n?i)?(a[i]?tmp)$

最后只需要对$dp[1]?dp[n]$求和。

采用线段树维护区间最大值$a[i]$的下标$i$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 50;
int n;
int a[MAXN];
ll f[MAXN];
struct Tr{
    int l, r, ans;
}tr[MAXN * 4];

void pushup(int u)
{
    if(a[tr[u << 1].ans] >= a[tr[u << 1 | 1].ans]) tr[u].ans = tr[u << 1].ans;
    else tr[u].ans = tr[u << 1 | 1].ans;
}

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

int query(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        return tr[u].ans;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(r <= mid) return query(u << 1, l, r);
    else if(l > mid) return query(u << 1 | 1, l, r);
    else{
        int ql = query(u << 1, l, mid), qr = query(u << 1 | 1, mid + 1, r);
        if(a[ql] >= a[qr]) return ql;
        else return qr;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; i++) scanf("%d", &a[i]);
    build(1, 1, n);

    f[n] = 0;
    ll ans = 0;
    for(int i = n - 1; i > 0; i --)
    {
         int tmp = query(1, i + 1, a[i]);
         f[i] = f[tmp] + (ll)((n - i) - (a[i] - tmp));
         ans += f[i];
    }
    printf("%lld\n", ans);

    return 0;
}

hdu 5634Problem - 5634 (hdu.edu.cn) （势能线段树）

题意：

给出一个长度为n的数组A，接下来有m次操作。
1 l r
对所有区间[l,r]中的整数i，把A[i]变成φ(A[i])(指欧拉函数)
2 l r x
对所有区间[l,r]中的整数i，把A[i]变成x
3 l r
询问[l,r]的区间和。

首先使用线性筛的方法计算出1e7内每个数的欧拉函数

我们知道，一个数在不断变成它的欧拉函数若干次之后恒为一，且许多数的欧拉函数值都是相同的（数据随机）。这样的话，如果我们将修改操作进行改进，只有在当前区间在询问区间以内且当前区间中的数都相同时，我们才对这个区间进行修改，否则我们继续对其的左右儿子进行修改，尽管看起来这种思路效率极低，但如果我们仔细分析会发现，一个区间中的数被1 , 2 操作修改若干次以后，都会变成相同的，因此这个算法的效率就有了保障，平摊下来差不多就$O（nlogn）$的时间复杂度。因此问题不大。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 50, M = 1e7 + 5;
int T, n, m, cnt;
ll a[MAXN], euler[M];

struct Tr{
    int l, r;
    ll lazy, sum;
}tr[MAXN * 4];

void get_euler() // 欧拉函数线性筛，不然会爆空间
{
    memset(euler, 0, sizeof(euler));
    euler[1] = 1;
    for(ll i = 2; i < M; i++)
    {
        if(!euler[i])
        {
            for(ll j = i; j < M; j += i)
            {
                if(!euler[j]) euler[j] = j;
                euler[j] = euler[j] / i * (i-1);
            }
        }
    }
}

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    if(tr[u << 1].lazy == tr[u << 1 | 1].lazy) tr[u].lazy = tr[u << 1].lazy;
    else tr[u].lazy = 0;
}

void pushdown(int u)
{
    if(tr[u].lazy)
    {
        tr[u << 1].lazy = tr[u << 1 | 1].lazy = tr[u].lazy;
        tr[u << 1].sum = (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].lazy;
        tr[u << 1 | 1].sum = (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].lazy;
    }
}

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

void change(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r && tr[u].lazy)
    {
        tr[u].sum = euler[tr[u].lazy] * (tr[u].r - tr[u].l + 1);
        tr[u].lazy = euler[tr[u].lazy];
        return;
    }
    pushdown(u); // 改变的时候也要pushdown
    int mid = (tr[u].r + tr[u].l) >> 1;
    if(l <= mid) change(u << 1, l, r);
    if(r > mid) change(u << 1 | 1, l, r);
    pushup(u);
}

void change2(int u, int l, int r, int k)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].sum = (ll)k * (tr[u].r - tr[u].l + 1); // 这个地方开LL不然会爆int
        tr[u].lazy = k;
        return ;
    }
    pushdown(u);	// 改变的时候也要pushdown
    int mid = (tr[u].r + tr[u].l) >> 1;
    if(l <= mid) change2(u << 1, l, r, k);
    if(r > mid) change2(u << 1 | 1, l, r, k);
    pushup(u);
}

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

int main()
{
    get_euler();
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        build(1, 1, n);
        for(int i = 1; i <= m; i++)
        {
            int op, l, r;
            scanf("%d%d%d", &op, &l, &r);
            if(op == 1) {
                change(1, l, r);
            }
            else if(op == 2) {
                int v;
                scanf("%d", &v);
                change2(1, l, r, v);
            }
            else {
                ll ans = query(1, l, r);
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}

HDU1542 （扫描线） Problem - 1542 (hdu.edu.cn)

首先这个扫描线算法解决的是什么问题？

• 主要解决的是ACM中的
  • 矩形面积问题
  • 矩形周长问题
  • 多边形面积问题

如果不用扫描线，则用矩形和减去矩形交集：
$( 20 ? 10 ) ? ( 20 ? 10 ) + ( 25 ? 15 ) ? ( 25.5 ? 15 ) ? ( 20 ? 15 ) ? ( 20 ? 15 ) = 180.0 $

优化方式

把矩形分成三个$(20?10)?(15?10)+(25.5?10)?(20?15)+(25.5?15)?(25?20)=180$

采取这个方法的好处

只需要从左往右扫，一步一更新即可

那这种方法需要有哪些信息呢？

1. 每个新矩形的的高度。
2. 每个新矩形的宽度。

那我们先从计算宽度说起

1. 其实计算宽度特简单。我们把垂直于x的边单独挑出来。

然后按照x的大小排个序，隔位相减就可以得到。如$K u a n [ 0 ] = 15 ? 10 ; K u a n [ 1 ] = 20 ? 15 ; $

那现在来计算矩形的高度

矩形高度怎么计算呢？这是整个扫描线最难理解的地方。

那现在来计算矩形的高度
矩形高度怎么计算呢？这是整个扫描线最难理解的地方。

我先问一个问题：为什么二号矩形的高是( 10 + ( 25.5 ? 20 ) )呢？

很直观的回答就是：那是因为得算上1号矩形高，再加上2号矩形多出来的部分

那为什么三号矩形的高是( (25.5 ? 10)-5 )呢？

那是因为得用2号矩形的高那部分减去，减掉2号矩形下面多出来的部分。

那为什么有时候“多出来”是加上一个值，有时候“多出来”是减掉一个值呢？
这个问题其实也是得到高度最核心的问题，就是“入边”和“出边”的问题。

定义：在同一个矩形内，从左往右看，第一条看到的边为“入边”，第二条看到的边为“出边”
其实所谓的从左往右（也可以是从上往下），就是扫描线的方向。
当从左往右扫，遇到入边的线，则对入边区间扫到进行+1操作，遇到出边，那么对出边区间进行-1操作，这样子就可以解释“有时候“多出来”是加上一个值，有时候“多出来”是减掉一个值”这个问题了！

凭借刚才获得的知识，我们来思考步骤

0. （出入边赋值已完成）
1. 第一条为入边，区间为[10,20]，则区间[10,20] +1(此时区间[10,20] = 1)
2. 查看整个域的区间，只有[10,20]有值，则$Kuan[0]?10=50$
3. 第二条边为入边，区间为[15,25.5]，则[15,25.5]+1(此时区间[10,15]=1,[15,20]=2,[20,25.5]=1)
4. 查看整个域区间，从[10,25.5]有值，则$Kuan[1]?(25.5?10)=77.5$
5. 第三条边为出边，区间从[10,20]，则[10,20]-1(此时区间为[15,25.5] = 1)
6. 查看整个区间，从[15,25.5]有值，则$Kuan[2]?(25.5?15)=52.5$
7. 第四条边为出边，区间从[15,25.5]，此时-1，整个区间没掉
8. 整个区间没值，遍历结束。

思路清晰之后，用线段树解决问题：

1. 将$y$坐标离散化。
2. 用一个区间数组记录每个区间的值：于是现在[10,15]成为块1，[15,20]成为块2，[20,25.5]成为块3。
3. 则现在更新第一条入边[10,20]就变成更新[1,3]，更新第二条边就变成更新[2,4]，之后再查表全部乘起来即可

int cover[maxn];//存放i节点对应覆盖情况的值
double length[maxn];//存放区间i下的总长度
double yy[maxn];//存放离散后的y值，下标用lowerbound进行查找

仔细观察，这棵树似乎和之前的线段树不一样，它的叶子节点的[l,r]不相等，而是差别为1。

这是因为点对于求面积的题目毫无意义，我们最需要的是它每一个基础的“块”。

1. 第一条为入边，区间为[1,3]，则区间cover[1,3] +1(此时区间[1,3] = 1)

2. query整个域的区间，得到len=10，则Kuan[0]*10 = 50

3. 第二条边为入边，区间为[2,4]，则cover[2,4]+1(此时如图所示)

4. query整个区间，得到len = 15.5，则Kuan[1]*(25.5-10) = 77.5

(注意：这里只需要上推len，不需要下推cover至[2,3]和[3,4]，也不需要上推cover至[1,4]。这就是线段树的强大之处：只要找到对应结点的区间能完全覆盖当前线段区间就可以回溯统计了，并不需要更新到叶子节点，这是线段树为什么效率高的原因)

5. 第三条边为出边，区间从[1,3]，则[1,3]-1
6. query整个区间，得到10.5，则Kuan[2]*10.5 = 52.5

7. 第四条边为出边，区间从[15,25.5]，此时-1，整个区间没掉
8. query整个区间，值为0，遍历结束。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
const int MAXN = 1e5 + 50;
vector<double>ys;
int n;

struct Seg{
    double x, y1, y2;
    int k;
    bool operator<(const Seg &t)const
    {
        return x < t.x;
    }
}S[MAXN * 2];

struct Tr{
    int l, r;
    int cnt;
    double len;
}tr[MAXN * 8];

int find(double x)
{
    return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}

void pushup(int u)
{
    if(tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[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)
{
    tr[u] = {l, r};
    if(l != r)
    {
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
}

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

int main()
{
    int T = 1;
    while(cin >> n && n)
    {
        for(int i = 0, j = 0; i < n; i++)
        {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            S[j ++] = {x1, y1, y2, 1};
            S[j ++] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2);
        }
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        build(1, 0, ys.size() - 2);
        
        sort(S, S + 2 * n);
        
        double res = 0;
        for(int i = 0; i < 2 * n; i++)
        {
            if(i > 0) res += tr[1].len * (S[i].x - S[i - 1].x);
            change(1, find(S[i].y1), find(S[i].y2) - 1, S[i].k);
        }
        printf("Test case #%d\n", T++);
        printf("Total explored area: %.2f\n\n", res);
    }
    return 0;
}

uva11983 (扫描线)

给你n个矩形，矩形的边与坐标轴平行，然后问你整个平面上被覆盖k次及以上的面积总和是多少

非常经典的扫描线

$Sum[rt][k]$表示区间rt被覆盖k次的长度是多少

先离散化，然后按照y轴建树

然后用x轴扫过去

问题是如果某个区间覆盖远超过k次，我们是没有记录远超过k次的区间覆盖的

这里有个小技巧 不需要把区间加减标记 pushdown

BZOJ1858 [Scoi2010]序列操作

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：

0 a b 把[a, b]区间内的所有数全变成0

1 a b 把[a, b]区间内的所有数全变成1

2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0

3 a b 询问[a, b]区间内总共有多少个1

4 a b 询问[a, b]区间内最多有多少个连续的1

对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？

1< = n, m < = 100000