前缀和，差分与离散化

世间温柔，不过是芳春柳摇染花香，槐序蝉鸣入深巷，白茂叶落醉故乡。

image-20240224203724480

荀子曰：不积跬步，无以至千里；不积小流，无以成江海。这句话揭示了世间万物整体和部 分之间的关系——庞大的整体由若干个体组成；单个个体虽小，但经过一点一滴的累积，也能聚 成一个庞大的整体。学习工作贵在不断积累，不断充实、丰富、完善自己，所有的努力都会有回报。

在算法竞赛中，利用整体和部分的性质可以达成很多目的，例如利用前缀和可以在常数时间 复杂度中查询区间和，利用差分在常数时间复杂度对序列进行区间操作，或者利用离散化去除无 用数据区间，通过放缩保留有用的数据。这些操作使得我们不必每次都要重复处理个体的数据， 而是直接对整体进行处理，从而降低时间复杂度，提升运算效率。这一章将会学习前缀和、差分 和离散化的思想，并使用这些思想完成一些简单的任务。

该题单内容将继续改进。

对应进阶篇第 2 章。

【深进1.例1】求区间和

题目描述

给定 \(n\) 个正整数组成的数列 \(a_1, a_2, \cdots, a_n\) 和 \(m\) 个区间 \([l_i,r_i]\)，分别求这 \(m\) 个区间的区间和。

对于所有测试数据，\(n,m\le10^5,a_i\le 10^4\)

输入格式

第一行，为一个正整数 \(n\) 。

第二行，为 \(n\) 个正整数 \(a_1,a_2, \cdots ,a_n\)

第三行，为一个正整数 \(m\) 。

接下来 \(m\) 行，每行为两个正整数 \(l_i,r_i\) ，满足\(1\le l_i\le r_i\le n\)

输出格式

共 \(m\) 行。

第 \(i\) 行为第 \(i\) 组答案的询问。

样例 #1

样例输入 #1

1
2
3
4
5
4
4 3 2 1
2
1 4
2 3

样例输出 #1

1
2
10
5

提示

样例解释：第 \(1\) 到第 \(4\) 个数加起来和为 \(10\)。第 \(2\) 个数到第 \(3\) 个数加起来和为 \(5\)。

对于 \(50 \%\) 的数据：\(n,m\le 1000\)；

对于 \(100 \%\) 的数据：\(1 \le n, m\le 10^5\)，\(1 \le a_i\le 10^4\)

image-20240216220751212 
1
2
3
4
前缀和其实就是用一个数组S存下数组a的前缀的和，这样话方便以后的查找，提高查找的速度。
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
遍历一遍数组a就可以得到我们的前缀和数组，所以前缀和的时间复杂度是O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//一维前缀和的简单应用，不需要解释
#include<iostream>
using namespace std;
const int N=1e5;
#define rep(i,a,n) for(int i=a;i<=n;i++)
int a[N];
int s[N];
int main()
{
int n;
cin>>n;
int m;
rep(i,1,n)
{
    cin>>a[i];
    s[i]=s[i-1]+a[i];
}
cin>>m;
rep(i,1,m)
{
    int x,y;
    cin>>x>>y;
    cout<<s[y]-s[x-1]<<'\n';
}
}

最大加权矩形

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 \(n\times n\) 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于 \([-127,127]\) ,例如

1
2
3
4
 0 –2 –7  0 
 9  2 –6  2
-4  1 –4  1 
-1  8  0 –2

在左下角：

1
2
3
9  2
-4  1
-1  8

和为 \(15\)。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行：\(n\)，接下来是 \(n\) 行 \(n\) 列的矩阵。

输出格式

最大矩形（子矩阵）的和。

样例 #1

样例输入 #1

1
2
3
4
5
4
0 -2 -7 0
 9 2 -6 2
-4 1 -4  1 
-1 8  0 -2

样例输出 #1

1
15

提示

\(1 \leq n\le 120\)

二维前缀和的时间复杂度其实可以类比一维的时间复杂度，就是把这个二维数组遍历一遍，这样的话就是O(n*m)的时间复杂度

我们只能先算出一个然后再减去重复的部分，最后我们可以得到

s[i] [j]=s[i-1] [j]+s[i] [j-1]-s[i-1] [j-1]+a[i] [j]

1
2
3
for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
           S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + a[i][j];

查询的话也是类似

s[x2] [y2]-s[x1-1] [y2]-s[x2] [y1-1]+s[x1-1] [y1-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//一道模板题，供给参考
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int a[N][N], s[N][N];

int main()
{
     int n, m, q;
     cin >> n >> m >> q;
     for (int i = 1; i <= n; i++)
     {
          for (int j = 1; j <= m; j++)
          {
               scanf("%d", &a[i][j]);
          }
     }
     for (int i = 1; i <= n; i++)
     {
          for (int j = 1; j <= m; j++)
          {
               s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
          }
     }
     while (q--)
     {
          int x1, x2, y1, y2;
          scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
          printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
     }
     return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//二维前缀和的简单应用，应该不需要解释了
#include<bits/stdc++.h>
using namespace std;
const int N=200;
int a[N][N];
int sum[N][N];
#define rep(i,a,n) for(int i=a;i<=n;i++)
using ll=long long;
int ans;
int main()
{
int n;
cin>>n;
rep(i,1,n)
{
    rep(j,1,n)
    {
        cin>>a[i][j];
        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];   
         }
}

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

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

            for (int l = j; l <= n; l++)
            {
                ans = max(sum[k][l] + sum[i - 1][j - 1] - sum[k][j - 1] - sum[i - 1][l], ans);
            }
        }
    }
}
cout<<ans;
}

[NOIP2011 提高组] 聪明的质监员

题目描述

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 \(n\) 个矿石，从 \(1\) 到 \(n\) 逐一编号，每个矿石都有自己的重量 \(w_i\) 以及价值 \(v_i\) 。检验矿产的流程是：

  1. 给定$ m$ 个区间 \([l_i,r_i]\)；
  2. 选出一个参数 \(W\)；
  3. 对于一个区间 \([l_i,r_i]\)，计算矿石在这个区间上的检验值 \(y_i\)：

\[y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j\]

其中 \(j\) 为矿石编号。

这批矿产的检验结果 \(y\) 为各个区间的检验值之和。即：\(\sum\limits_{i=1}^m y_i\)

若这批矿产的检验结果与所给标准值 \(s\) 相差太多，就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产，所以他想通过调整参数 \(W\) 的值，让检验结果尽可能的靠近标准值 \(s\)，即使得 \(|s-y|\) 最小。请你帮忙求出这个最小值。

输入格式

第一行包含三个整数 \(n,m,s\)，分别表示矿石的个数、区间的个数和标准值。

接下来的 \(n\) 行，每行两个整数，中间用空格隔开，第 \(i+1\) 行表示 \(i\) 号矿石的重量 \(w_i\) 和价值 \(v_i\)。

接下来的 \(m\) 行，表示区间，每行两个整数，中间用空格隔开，第 \(i+n+1\) 行表示区间 \([l_i,r_i]\) 的两个端点 \(l_i\) 和 \(r_i\)。注意：不同区间可能重合或相互重叠。

输出格式

一个整数，表示所求的最小值。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
5 3 15 
1 5 
2 5 
3 5 
4 5 
5 5 
1 5 
2 4 
3 3

样例输出 #1

1
10

提示

【输入输出样例说明】

当 \(W\) 选 \(4\) 的时候，三个区间上检验值分别为 \(20,5 ,0\) ，这批矿产的检验结果为 \(25\)，此时与标准值 \(S\) 相差最小为 \(10\)。

【数据范围】

对于 $10% $ 的数据，有 \(1 ≤n ,m≤10\)；

对于 $30% $的数据，有 \(1 ≤n ,m≤500\) ；

对于 $50% $ 的数据，有 $ 1 ≤n ,m≤5,000$；

对于 \(70\%\) 的数据，有 \(1 ≤n ,m≤10,000\) ；

对于 \(100\%\) 的数据，有 $ 1 ≤n ,m≤200,000$，\(0 < w_i,v_i≤10^6\)，\(0 < s≤10^{12}\)，\(1 ≤l_i ≤r_i ≤n\) 。

W越大，矿石选的越少，W越小，矿石选的越多。 $$ 当

Y>s 时，需要增大

W来减小

Y,从而

∣Y−s∣变小；

当

Y==s时，

∣Y−s∣==0;

当

Y，从而

∣Y−s∣变大； $$ 我们在计算一个区间的和时

通常是用前缀和的方法来缩减时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// P1314 [NOIP2011 提高组] 聪明的质监员
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
ll n,m,s;
const int N=2e6;
ll a[N];
ll v[N];
ll w[N];
ll vx[N];
ll wx[N];
ll cmin=1e15;
ll cmax;
ll value;
ll ans=1e15;
//本题思路是二分去枚举那个w，然后用个数×求和，记录一个个数组，再记录一个价值数组
//如果价值比较大，就要扩大w
//如果价值比较小，就要缩小w
struct node
{
    ll l;
    ll r;
}q[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s;
    rep(i,1,n)
    {
        cin>>w[i]>>v[i];
        cmin=min(cmin,w[i]);
        cmax=max(cmax,w[i]);
    }
    //取最大值再取最小值
    //作为二分边界罢
    ll r=cmax+1;
    ll l=cmin-1;
    ll mid;
    rep(i,1,m)
    {
        cin>>q[i].l>>q[i].r;
    }
    //输入，用结构体存储
    while(l<r)
    {
        memset(vx, 0, sizeof(vx));
        memset(wx, 0, sizeof(wx));
        //多测清零
        value=0;
        ll mid=(l+r)/2;
        rep(i,1,n)
        {
            if(w[i]>=mid)
            {
                vx[i]=vx[i-1]+v[i];
                wx[i]=wx[i-1]+1;
            }
            else{
                vx[i]=vx[i-1];
                wx[i]=wx[i-1];
            }
        }
        //两组前缀和
            rep(i,1,m)
            {
        value+=(vx[q[i].r]-vx[q[i].l-1])*(wx[q[i].r]-wx[q[i].l-1]);
            }
            if(value>s)
            {
                l=mid+1;
            }
            else
            {
                r=mid;
            }
        ans=min(abs((value-s)),ans);
        //记录答案
    }
cout<<ans;
    return 0;
}

语文成绩

题目背景

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 \(n\)，\(p\)，代表学生数与增加分数的次数。

第二行有 \(n\) 个数，\(a_1 \sim a_n\)，代表各个学生的初始成绩。

接下来 \(p\) 行，每行有三个数，\(x\)，\(y\)，\(z\)，代表给第 \(x\) 个到第 \(y\) 个学生每人增加 \(z\) 分。

输出格式

输出仅一行，代表更改分数后，全班的最低分。

样例 #1

样例输入 #1

1
2
3
4
3 2
1 1 1
1 2 1
2 3 1

样例输出 #1

1
2

提示

对于 \(40\%\) 的数据，有 \(n \le 10^3\)。

对于 \(60\%\) 的数据，有 \(n \le 10^4\)。

对于 \(80\%\) 的数据，有 \(n \le 10^5\)。

对于 \(100\%\) 的数据，有 \(n \le 5\times 10^6\)，\(p \le n\)，学生初始成绩 $ \(，\)z $。

（学了爬虫一定要把题目Md格式给爬了，草），不用爬了，5天后的你找到了解决方案，又为不学爬虫找了个借口 $$ 对于一个数列 ai

，我们需要维护的数据是“相邻两个数之差”。这种策略是，令pi=△ai=a_i−a_(i−1)

=即相邻两数的差。我们称数列 pi

为数列 ai

的差分数列。 $$ 原数组：1,2,3,4,51,2,3,4,5。

其对应的差分数组：1,1,1,1,11,1,1,1,1。

可以发现，原数组的前缀和的差分就是原数组，原数组的差分的前缀和也是原数组，所以差分和前缀和是一对互逆的运算。

至于加和减去的操作很好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//一阶差分
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
int ans=1e9;
const int N = 2e7;
int a[N];
int cha[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
    cha[i]=a[i]-a[i-1];
}
rep(i,1,m)
{
    int x,y,z;
    cin>>x>>y>>z;
    cha[x]+=z;
    cha[y+1]-=z;
}
rep(i,1,n)
{
    a[i]=cha[i]+a[i-1];
    ans=min(ans,a[i]);
}
cout<<ans;
}

地毯

题目描述

在 \(n\times n\) 的格子上有 \(m\) 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 \(n,m\)。意义如题所述。

接下来 \(m\) 行，每行两个坐标 \((x_1,y_1)\) 和 \((x_2,y_2)\)，代表一块地毯，左上角是 \((x_1,y_1)\)，右下角是 \((x_2,y_2)\)。

输出格式

输出 \(n\) 行，每行 \(n\) 个正整数。

第 \(i\) 行第 \(j\) 列的正整数表示 \((i,j)\) 这个格子被多少个地毯覆盖。

样例 #1

样例输入 #1

1
2
3
4
5 3
2 2 3 3
3 3 5 5
1 2 1 4

样例输出 #1

1
2
3
4
5
0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

提示

样例解释

覆盖第一个地毯后：

\(0\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(0\) \(0\) \(0\)

覆盖第一、二个地毯后：

\(0\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(2\) \(1\) \(1\)
\(0\) \(0\) \(1\) \(1\) \(1\)
\(0\) \(0\) \(1\) \(1\) \(1\)

覆盖所有地毯后：

\(0\) \(1\) \(1\) \(1\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(2\) \(1\) \(1\)
\(0\) \(0\) \(1\) \(1\) \(1\)
\(0\) \(0\) \(1\) \(1\) \(1\)

数据范围

对于 \(20\%\) 的数据，有 \(n\le 50\)，\(m\le 100\)。

对于 \(100\%\) 的数据，有 \(n,m\le 1000\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// P3397 地毯
//二阶差分
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N=5e3;
int d[N][N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    rep(i,1,m)
 {
    int x1,x2,y1,y2;
    cin>>x1>>y1>>x2>>y2;
    d[x1][y1]+=1;
    d[x1][y2+1]-=1;
    d[x2+1][y1]-=1;
    d[x2+1][y2+1]+=1;
        //进行差分意义下的加减
 }
 for (int i = 1; i <= n; i++)
 {
     for (int j = 1; j <= n; ++j)
     {
         d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
         //求前缀和
         cout << d[i][j] << ' ';
     }
     cout << '\n';
 }
}

火烧赤壁

题目背景

曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。

孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。

隆冬的十一月，天气突然回暖，刮起了东南风。

没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。

曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！

题目描述

给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。

输入格式

第一行一个整数，表示起火的信息条数 \(n\)。
接下来 \(n\) 行，每行两个整数 \(a, b\)，表示一个着火位置的起点和终点（注意：左闭右开）。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
3
-1 1
5 11
2 9

样例输出 #1

1
11

提示

数据规模与约定

对于全部的测试点，保证 \(1 \leq n \leq 2 \times 10^4\)，\(-2^{31} \leq a \leq b \lt 2^{31}\)，且答案小于 \(2^{31}\)。

离散化

解释一下离散化这个思想（算法？）

　离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。这是百度百科上的定义。

离散化是对一堆元素进行操作，通过改变他们的大小，但不改变他们的大小关系，这种做法往往可以节省空间，减低时空复杂度。

某个题目告诉你有1e5个数，每个数大小不超过1e9，要你对这些数进行操作（比如并查集之类的）。那么肯定不能直接开1e9大小的数组，但是1e5的范围就完全没问题。在举个栗子，现在对{4,7,6,9}进行离散化，那么得到的结果是{1,3,2,4}，也就是说，当我们并不需要这些数据具体是多少时，就只需要知道他们的相对大小就行了。

好比本题火烧赤壁。

离散化常见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int N=1e5+7;
int t[N],a[N];
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>a[i],t[i]=a[i];
  sort(t+1,t+n+1);
  m=unique(t+1,t+n+1)-t-1;
  for(int i=1;i<=n;i++)
    a[i]=lower_bound(t+1,t+m+1,a[i])-t;
}
//在这段代码中，a[]经过离散，范围就变成了m。解释一下，unique是c++自带的一个函数，表示对一个数列去重，然后返回不重复的元素个数，当然在后面要减去首地址。那么这种离散化对于有重复元素的数列也可以适用

//这种是以结构体来离散化的
    const int N=1e5+7;
    struct Node{
      int v,id;
      bool operator < (const Node a)const{
        return v<a.v;}//排序用
    }a[N];
    int n,rank[N];
    int main()
    {
      cin>>n;
      for(int i=1;i<=n;i++){
        cin>>a[i].v;
        a[i].id=i;}
      sort(a+1,a+n+1);
      for(int i=1;i<=n;i++)
        rank[a[i].id]=i;
    }

//vector版本
// std::vector<int> arr;
std::vector<int> tmp(arr);  // tmp 是 arr 的一个副本
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; ++i)
  arr[i] = std::lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// P1496 火烧赤壁
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N=2e6;
ll a[N];
ll b[N];
ll ans;
ll dtop;
ll ctop;
ll d[N];
ll c[N];
ll f[N];
int main()
{
int n;
cin>>n;
rep(i,1,n)
{
cin>>a[i]>>b[i];
d[++dtop]=a[i];
d[++dtop]=b[i];
}
 //先进行记录
sort(d+1,d+1+dtop);
    //排序
rep(i,1,dtop)
{
    if(d[i]!=d[i-1]||i==1)
    {
        c[++ctop]=d[i];
    }
}
    //去重
//综上为离散的过程
rep(i,1,n)
{
    int x=lower_bound(c+1,c+ctop+1,a[i])-c;
    int y=lower_bound(c+1,c+ctop+1,b[i])-c;
    //查询
rep(j,x,y-1)
{
    f[j]=1;
}
}
rep(i,1,ctop-1)
{
    if(f[i])
    {
        ans+=c[i+1]-c[i];
    }
}
cout<<ans;
}
1
2
3
4
5
6
7
8
9
10
11
//下一题的小小铺垫
# 并查集的Get操作
int get(int x){
	if(x==fa[x])	return x;
    return fa[x]=get(fa[x]);//路径压缩
}
# 并查集的Merge操作
void merge(int x,int y){
	fa[get(x)]=get(y);
} // 可以直接写在程序里
并查集一定要初始化，即fa[i]=i，表示i的爹是它自己

[NOI2015] 程序自动分析

题目描述

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设 \(x_1,x_2,x_3,\cdots\) 代表程序中出现的变量，给定 \(n\) 个形如 \(x_i=x_j\) 或 \(x_i\neq x_j\) 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：\(x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1\)，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

输入的第一行包含一个正整数 \(t\)，表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第一行包含一个正整数 \(n\)，表示该问题中需要被满足的约束条件个数。接下来 \(n\) 行，每行包括三个整数 \(i,j,e\)，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 \(e=1\)，则该约束条件为 \(x_i=x_j\)。若\(e=0\)，则该约束条件为 \(x_i\neq x_j\)。

输出格式

输出包括 \(t\) 行。

输出文件的第 \(k\) 行输出一个字符串 YES 或者 NO（字母全部大写），YES 表示输入中的第 \(k\) 个问题判定为可以被满足，NO 表示不可被满足。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

样例输出 #1

1
2
NO
YES

样例 #2

样例输入 #2

1
2
3
4
5
6
7
8
9
10
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

样例输出 #2

1
2
YES
NO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105


//P1955[NOI2015] 程序自动分析
//本题考查并查集和离散化
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N=1e6;
struct node{
    int x,y,z;
}a[N];
int b[N];
int c[N];
int fa[N];
int find(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
{
    fa[x]=y;
}
}
//并查集实现
int n;
int main()
{
int t;
cin>>t;
    //输入
while(t--)
{
    cin>>n;
    int btop=0;
    int ctop=0;
    rep(i,1,n)
{
    cin>>a[i].x>>a[i].y>>a[i].z;
    b[++btop]=a[i].x;
    b[++btop]=a[i].y;
}
    //输入，开个结构体，并且实现第一步离散化
sort(b+1,b+1+btop);
    //第二步离散化，排序
rep(i,1,btop)
{
    if(b[i]!=b[i-1]||i==1)
    {
        c[++ctop]=b[i];
    }
}
    //第三步离散化去重
rep(i,1,n)
{
    a[i].x=lower_bound(c+1,c+1+ctop,a[i].x)-c;
    a[i].y=lower_bound(c+1,c+1+ctop,a[i].y)-c;
}
    //第四步离散化，二分记录
rep(i,1,ctop)
{
    fa[i]=i;
}
    //并查集初始化
rep(i,1,n)
{
    if(a[i].z)
    {
        merge(a[i].x,a[i].y);
    }
}
    //如果是相等，请合并
bool mk=1;
rep(i,1,n)
{
    if(!a[i].z)
    {
        if(find(a[i].x)==find(a[i].y))
        {
            mk=0;
        }
    }
}
    //如果不相等的两个数出现在了一个集合里，那么请拜拜楼
if(mk)
{
    cout<<"YES"<<'\n';
}
else
{
    cout<<"NO"<<'\n';
}

}
}
//本题结束

[USACO12FEB] Overplanting S

题目描述

Farmer John has purchased a new machine that is capable of planting grass within any rectangular region of his farm that is "axially aligned" (i.e., with vertical and horizontal sides). Unfortunately, the machine malfunctions one day and plants grass in not one, but N (1 <= N <= 1000) different rectangular regions, some of which may even overlap.

Given the rectangular regions planted with grass, please help FJ compute the total area in his farm that is now covered with grass.

在一个笛卡尔平面坐标系里（则X轴向右是正方向，Y轴向上是正方向），有N(\(1<=N<=1000\))个矩形，第i个矩形的左上角坐标是(x1, y1),右下角坐标是（x2,y2）。问这N个矩形所覆盖的面积是多少？注意：被重复覆盖的区域的面积只算一次。

输入格式

第一行，一个整数Ｎ。 (\(1<=N<=1000\))。

接下来有N行，每行描述一个矩形的信息，分别是矩形的x1、y1、x2、y2。

其中 \(-10^8<=x1,y1,x2,y2<=10^8\)。

输出格式

一个整数，被N个矩形覆盖的区域的面积。

样例 #1

样例输入 #1

1
2
3
2
0 5 4 1
2 4 6 2

样例输出 #1

1
20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// P1884 [USACO12FEB] Overplanting S
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N = 5050;
using namespace std;
int n;
int btop;
int ctop;
int a[N][4];
int b[N];
int c[N];
int f[N][N];
map<int,int>Map;
int main()
{
cin>>n;
rep(i,1,n)
{
    rep(j,0,3)
    {
        cin>>a[i][j];
        b[++btop]=a[i][j];//记录
    }
}
sort(b+1,b+btop+1);//排序
b[0]=-1000000007;
rep(i,1,btop)
{
    if(b[i]!=b[i-1])
    {
        c[++ctop]=b[i];
        Map[b[i]]=ctop;
    }
}
//离散化
rep(i,1,n)
{
    rep(j,0,3)
    {
a[i][j]=Map[a[i][j]];//记录值
    }
}
rep(k,1,n)
{
    rep(i,a[k][0],a[k][2]-1)
    {
        f[i][a[k][3]]++;
        f[i][a[k][1]]--;
    }
}
rep(i,1,ctop-1)
{
    rep(j,1,ctop-1)
    {
        f[i][j]+=f[i][j-1];
    }
}
ll ans=0;
rep(i,1,ctop-1)
{
    rep(j,1,ctop-1)
    {
        if(f[i][j])
        {
            ans+=1ll*(c[i+1]-c[i])*(c[j+1]-c[j]);
        }
    }
}
cout<<ans;
}

领地选择

题目描述

作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地 \(C\times C\) 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

输入格式

第一行三个整数 \(N,M,C\)，表示地图的宽和长以及首都的边长。

接下来 \(N\) 行每行 \(M\) 个整数，表示了地图上每个地块的价值。价值可能为负数。

输出格式

一行两个整数 \(X,Y\)，表示首都左上角的坐标。

样例 #1

样例输入 #1

1
2
3
4
3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1

样例输出 #1

1
1 2

提示

对于 \(60\%\) 的数据，\(N,M\le 50\)。

对于 \(90\%\) 的数据，\(N,M\le 300\)。

对于 \(100\%\) 的数据，\(1\le N,M\le 10^3\)，\(1\le C\le \min(N,M)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//非常普通的二维前缀和罢了
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int Max = 1003;
int a[Max][Max];
int f[Max][Max];
signed main()
{
	int n, m, c;
	cin >> n >> m >> c;
	for ( int i = 1; i <= n; ++i)
		for ( int j = 1; j <= m; ++j)
			cin >> a[i][j], f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
   //二维前缀和
	int M = 0, x, y;
	for ( int i = c; i <= n; ++i)
		for ( int j = c; j <= m; ++j)
			if (f[i][j] + f[i - c][j - c] - f[i - c][j] - f[i][j - c] > M)
			{
				int acioi = f[i][j] + f[i - c][j - c] - f[i - c][j] - f[i][j - c];
				M = acioi;
				x = i, y = j;
			}
    //记录位置
	cout << x - c + 1 << " " << y - c + 1 << '\n';

}

[USACO11MAR] Brownie Slicing G

题面翻译

Bessie烘焙了一块巧克力蛋糕。这块蛋糕是由 \(R\times C(1\leq R,C\leq 500)\) 个小的巧克力蛋糕组成的。第 \(i\) 行，第 \(j\) 列的蛋糕有 \(N_{i,j}(N_{i,j}\leq 4000)\) 块巧克力碎屑。

Bessie想把蛋糕分成 \(A\times B(1\leq A\leq R,1\leq B\leq C)\) 块，:给 \(A\times B\) 只奶牛。蛋糕先水平地切 \(A-1\) 刀（只能切沿整数坐标切）来把蛋糕划分成 \(A\) 块。然后再把剩下来的每一块独立地切 \(B-1\) 刀，也只能切沿整数坐标切。其他 \(A\times B-1\) 只奶牛就每人选一块，留下一块给Bessie。由于贪心，他们只会留给Bessie巧克力碎屑最少的那块。求出Bessie最优情况下会获得多少巧克力碎屑。

例如，考虑一个\(5\times4\)的蛋糕，上面的碎屑分布如下图所示：

1
2
3
4
5
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

Bessie必须把蛋糕切成4条，每条分成2块。Bessie能像这样切蛋糕:

1
2
3
4
5
6
7
8
1 2 | 2 1
---------
3 | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1

这样，Bessie至少能获得 \(3\) 块巧克力碎屑

题目描述

Bessie has baked a rectangular brownie that can be thought of as an RxC grid (1 <= R <= 500; 1 <= C <= 500) of little brownie squares. The square at row i, column j contains N_ij (0 <= N_ij <= 4,000) chocolate chips.

Bessie wants to partition the brownie up into A*B chunks (1 <= A <= R; 1 <= B <= C): one for each of the A*B cows. The brownie is cut by first making A-1 horizontal cuts (always along integer

coordinates) to divide the brownie into A strips. Then cut each strip *independently* with B-1 vertical cuts, also on integer

boundaries. The other A*B-1 cows then each choose a brownie piece, leaving the last chunk for Bessie. Being greedy, they leave Bessie the brownie that has the least number of chocolate chips on it.

Determine the maximum number of chocolate chips Bessie can receive, assuming she cuts the brownies optimally.

As an example, consider a 5 row x 4 column brownie with chips

distributed like this:

1
2
3
4
5
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

Bessie must partition the brownie into 4 horizontal strips, each with two pieces. Bessie can cut the brownie like this:

1
2
3
4
5
6
7
8
1 2 | 2 1
---------
3 | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1

Thus, when the other greedy cows take their brownie piece, Bessie still gets 3 chocolate chips.

Bessie烘焙了一块巧克力蛋糕。这块蛋糕是由R*C(1 <= R,C <= 500)个小的巧克力蛋糕组成的。第i行，第j列的蛋糕有N_ij(1<= N_ij <= 4,000)块巧克力碎屑。

Bessie想把蛋糕分成A*B块，(1 <= A<= R,1 <= B <= C): 给A*B只奶牛。蛋糕先水平地切A-1刀（只能切沿整数坐标切）来把蛋糕划分成A块。然后再把剩下来的每一块独立地切B-1刀，也只能切沿整数坐标切。其他A*B-1只奶牛就每人选一块，留下一块给Bessie。由于贪心，他们只会留给Bessie巧克力碎屑最少的那块。求出Bessie最优情况下会获得多少巧克力碎屑。

例如，考虑一个5*4的蛋糕，上面的碎屑分布如下图所示：

1
2
3
4
5
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

Bessie必须把蛋糕切成4条，每条分成2块。Bessie能像这样切蛋糕:

输入格式

* Line 1: Four space-separated integers: R, C, A, and B

* Lines 2..R+1: Line i+1 contains C space-separated integers: N_i1, ..., N_iC

输出格式

* Line 1: A single integer: the maximum number of chocolate chips that Bessie guarantee on her brownie

样例 #1

样例输入 #1

1
2
3
4
5
6
5 4 4 2 
1 2 2 1 
3 1 1 1 
2 0 1 3 
1 1 1 1 
1 1 1 1

样例输出 #1

1
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//二分加前缀和，注意刀法
#include<bits/stdc++.h>
using namespace std;
const int N = 1000;
int n, m, a, b, l, r, ans, s[N][N];
bool check(int x) 
{
	int tmp = 0, now = 0;
    //水平切的条数
    //和当前到哪条了
	for (int i = 1; i <= n; i++) 
	{
		int k = 0;
        //竖直能不能切成条
		for (int j = 1, lst = 0; j <= m; j++)
            //二维前缀和，注意两个初始化，一个是now，会随着切刀改变，而Lst每经过一层内循环都会变为0，而且k是要满足>=b的
			if (s[i][j] - s[i][lst] - s[now][j] + s[now][lst] >= x) {//是否能切成一块
				k++;
				lst = j;
			}
		if (k >= b) 
		{
			tmp++;
            //+1刀水平的
			now = i;
            //更新now
		}
	}
	return tmp >= a;
    //如果切了很多刀还能行，证明还能再大一些
}
int main() {
	cin >> n >> m >> a >> b;
	for (int i = 1; i <= n; i++)
		for (int j = 1, x; j <= m; j++) 
		{
			cin >> x;
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;//计算前缀和
		}
	r = s[n][m];
    //最大的答案
    //以下是二分
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid))
            //如果满足
        {
            //答案可以再大一点
			ans = mid;
			l = mid + 1;
		}
        //答案再小一点
		else r = mid - 1;
	}
	cout << ans << '\n';
}

海底高铁

题目描述

该铁路经过 \(N\) 个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第 \(i\) 段铁路连接了城市 \(i\) 和城市 \(i+1(1\leq i<N)\)。如果搭乘的比较远，需要购买多张车票。第 \(i\) 段铁路购买纸质单程票需要 \(A_i\) 博艾元。

虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了 IC 卡。对于第 \(i\) 段铁路，需要花 \(C_i\) 博艾元的工本费购买一张 IC 卡，然后乘坐这段铁路一次就只要扣 \(B_i(B_i<A_i)\) 元。IC 卡可以提前购买，有钱就可以从网上买得到，而不需要亲自去对应的城市购买。工本费不能退，也不能购买车票。每张卡都可以充值任意数额。对于第 \(i\) 段铁路的 IC 卡，无法乘坐别的铁路的车。

Uim 现在需要出差，要去 \(M\) 个城市，从城市 \(P_1\) 出发分别按照 \(P_1,P_2,P_3,\cdots,P_M\) 的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。

现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。

输入格式

第一行两个整数，\(N,M\)。

接下来一行，\(M\) 个数字，表示 \(P_i\)。

接下来 \(N-1\) 行，表示第 \(i\) 段铁路的 \(A_i,B_i,C_i\)。

输出格式

一个整数，表示最少花费

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10

样例输出 #1

1
6394

提示

\(2\) 到 \(3\) 以及 \(8\) 到 \(9\) 买票，其余买卡。

对于 \(30\%\) 数据 \(M=2\)。

对于另外 \(30\%\) 数据 \(N\leq1000，M\leq1000\)。

对于 \(100\%\) 的数据 \(M,N\leq 10^5，A_i,B_i,C_i\le10^5\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//对于每一段路求一个类似差分的东西，然后结合题意进行前缀和，因为车是从低往高坐的，而且每一段车要么买单程要么用卡，这样就可以了
#include<bits/stdc++.h>
using namespace std;
int n,m,c[100005],p2,p1,a,b,c1;
long long sum,ans;
int main()
{
	cin>>n>>m;
	if(m>0)cin>>p1;
	for(int i=2;i<=m;i++)
	{
		cin>>p2;
	 	if(p1<p2)c[p1]++,c[p2]--;
	 	else c[p2]++,c[p1]--;
	 	p1=p2;
	}
	for(int i=1;i<n;i++)
	{
		sum+=c[i];
		cin>>a>>b>>c1;
		if(sum!=0)ans+=min(a*sum,b*sum+c1);
	}
	if(m<=1)ans=0;
	cout<<ans;
	return 0;
}

[NOIP2012 提高组] 借教室

题目描述

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 \(n\) 天的借教室信息，其中第 \(i\) 天学校有 \(r_i\) 个教室可供租借。共有 \(m\) 份订单，每份订单用三个正整数描述，分别为 \(d_j,s_j,t_j\)，表示某租借者需要从第 \(s_j\) 天到第 \(t_j\) 天租借教室（包括第 \(s_j\) 天和第 \(t_j\) 天），每天需要租借 \(d_j\) 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 \(d_j\) 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 \(s_j\) 天到第 \(t_j\) 天中有至少一天剩余的教室数量不足 \(d_j\) 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 \(n,m\)，表示天数和订单的数量。

第二行包含 \(n\) 个正整数，其中第 \(i\) 个数为 \(r_i\)，表示第 \(i\) 天可用于租借的教室数量。

接下来有 \(m\) 行，每行包含三个正整数 \(d_j,s_j,t_j\)，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 \(1\) 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 \(0\)。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 \(-1\)，第二行输出需要修改订单的申请人编号。

样例 #1

样例输入 #1

1
2
3
4
5
4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4

样例输出 #1

1
2
-1 
2

提示

【输入输出样例说明】

第 $1 $份订单满足后，$4 $天剩余的教室数分别为 \(0,3,2,3\)。第 \(2\) 份订单要求第 $2 $天到第 \(4\) 天每天提供$ 3 $个教室，而第 \(3\) 天剩余的教室数为$ 2$，因此无法满足。分配停止，通知第\(2\) 个申请人修改订单。

【数据范围】

对于10%的数据，有\(1≤ n,m≤ 10\)；

对于30%的数据，有\(1≤ n,m≤1000\)；

对于 70%的数据，有\(1 ≤ n,m ≤ 10^5\)；

对于 100%的数据，有\(1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n\)。

NOIP 2012 提高组 第二天 第二题

2022.2.20 新增一组 hack 数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
int n,m;
const int N=1e6+10;
ll a[N];
ll d[N];
ll s[N];
ll t[N];
ll h[N];
ll c[N];
bool isok(ll x)
{
	memset(h,0,sizeof(h));
	for(int i=1;i<=x;i++)
	{
		h[s[i]]+=d[i];
		h[t[i]+1]-=d[i];	
	}
	for(int i=1;i<=n;i++)
	{
		c[i]=c[i-1]+h[i];
		if(c[i]>a[i])
		{
			return 0;
		}		
	}
	return 1;	
}
//差分+前缀和进行判断合理性
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>d[i]>>s[i]>>t[i];
		
	}
	if(isok(m))
	{
		cout<<0;
		return 0;
	}
	ll l=1;
	ll r=m;
	ll mid;
	while(l<r)
	{
		mid=(l+r)/2;
		if(isok(mid))
		{
			l=mid+1;	
		}
		else{
			r=mid;
		}	
	}//二分查看需要修改的人
		cout<<"-1"<<"\n"<<l;
	return 0; 	
}

[USACO07MAR] Face The Right Way G

题目描述

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

\(N\) 头牛排成一列 \(1 \le N \le 5000\)。每头牛或者向前或者向后。为了让所有牛都面向前方，农夫每次可以将 \(K\) 头连续的牛转向 \(1 \le K \le N\)，求使操作次数最小的相应 \(K\) 和最小的操作次数 \(M\)。\(F\) 为朝前，\(B\) 为朝后。

请在一行输出两个数字 \(K\) 和 \(M\)，用空格分开。

输入格式

Line 1: A single integer: N

Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

输出格式

Line 1: Two space-separated integers: K and M

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
7
B
B
F
B
F
B
B

样例输出 #1

1
3 3

提示

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)

本题贪心策略为：

从左到右对于出现的每一个B翻转一次从当前点开始的区间，就能保证是最优解。

有一个翻转的知识点：

什么时候会是没有用的呢？就是说我们这个是失败的，就是翻转到最后，已经后面没有东西可以让我们翻转了，就已经不够了

那我们这么模拟这个翻转的过程呢，也正是我所学到的东西，这个翻转的过程可以通过异或取得，我们首先将所有数字01化，这时候异或就起了妙用

任何数字异或0等于本身的道理

还有借助一个中间变量

我们就可以完美模拟这个翻转的过程

具体如下： 首先有一个B数组，里面都是0

有一个b初始化为0

如果一开始这头牛是0，也就是是背面，异或0就是0，那么！号后，就需要翻转了，翻转后b进行变换，代表接下来每头牛都会被翻转，这怎么行呢，那我们就需要对B[i+len]进行一次异或，让他回来，因为这个点是不能变化的

有点像差分对吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
bool A[N], B[N];
int main() {
	cin >> n;
	char ch;
	for (int i = 1; i <= n; ++i) 
	{
		cin >> ch; A[i] = ch == 'B' ? 0 : 1;
	}
	int mincnt = 0x7fffffff, anslen;
	for (int len = 1; len <= n; ++len) 
	{
		memset(B, 0, sizeof B);
		bool b = 0, flag = 1; int cnt = 0;
		for (int i = 1; i <= n; ++i) 
		{
			b ^= B[i];
			if (!(A[i] ^ b)) 
			{
				if (i + len - 1 > n) 
				{
					flag = 0; 
					break; 
				}
				b ^= 1, B[i + len] ^= 1;
				++cnt;
			}
		}
		if (flag) 
		{
			if (cnt < mincnt)
				mincnt = cnt, anslen = len; 
		}
	}
	cout<< anslen<<" "<<mincnt;
}

[Poetize6] IncDec Sequence

题目描述

给定一个长度为 \(n\) 的数列 \({a_1,a_2,\cdots,a_n}\)，每次可以选择一个区间\([l,r]\)，使这个区间内的数都加 \(1\) 或者都减 \(1\)。

请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

输入格式

第一行一个正整数 \(n\)
接下来 \(n\) 行,每行一个整数,第 $i+1 $行的整数表示 \(a_i\)。

输出格式

第一行输出最少操作次数
第二行输出最终能得到多少种结果

样例 #1

样例输入 #1

1
2
3
4
5
4
1
1
2
2

样例输出 #1

1
2
1
2

提示

对于 \(100\%\) 的数据，\(n\le 100000, 0 \le a_i \le 2^{31}\)。

取x,y，使得x为c中所有整数之和，y为c中所有负数之和再取反。观察前面的结论，我们可以把操作分成两部分：先是正负抵消，剩下的最后一个数，再单独把这个数递减（或加）到零，所以操作次数就是max(x,y) \[ ans=abs(min(X,Y))+abs(X−Y) \]

\[ ans=abs(max(X,Y)) \]

第二问： \[ ans=abs(X−Y)+1 \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 #include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e6+10;
ll a[N];
ll cha[N];
ll n;
ll q,p;
int main()
{
	cin>>n;
	cin>>a[1];
	for(int i=2;i<=n;i++)
	{
		cin>>a[i];
		cha[i]=a[i]-a[i-1];
		if(cha[i]>0)
		{
			q+=cha[i];
		}
		else{
			p-=cha[i];
		}
	}
	cout<<max(q,p)<<'\n';
	cout<<abs(q-p)+1;	
}

[USACO11NOV] Cow Lineup S

题面翻译

问题描述

农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种，他喜欢他的照片包含每

个品种的至少一头牛。

约翰的牛都站在一条沿线的不同地方， 每一头牛由一个整数位置 \(X_i\) 以及整数品种编号 \(ID_i\) 表示。

约翰想拍一张照片，这照片由沿线的奶牛的连续范围组成。照片的成本与规模相当，这就意味着，在一

系列照片中的最大和最小 \(X\) 坐标的差距决定了照片的成本。

请帮助约翰计算最小的照片成本，这些照片中有每个不同的品种的至少一头牛，没有两头牛愿意站

在同一个地点的。

输入格式

第 \(1\) 行：牛的数量 \(N\)；

第 \(2..1+N\) 行：每行包含 2 个以空格分隔的正整数 \(X_i\) 和 \(ID_i\)；意义如题目描述；

输出格式

输出共一行，包含每个不同品种 \(\rm ID\) 的照片的最低成本。

题目描述

Farmer John has hired a professional photographer to take a picture of some of his cows. Since FJ's cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.

FJ's N cows are all standing at various positions along a line, each described by an integer position (i.e., its x coordinate) as well as an integer breed ID. FJ plans to take a photograph of a contiguous range of cows along the line. The cost of this photograph is equal its size -- that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.

Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ's herd.

输入格式

* Line 1: The number of cows, N (1 <= N <= 50,000).

* Lines 2..1+N: Each line contains two space-separated positive integers specifying the x coordinate and breed ID of a single cow. Both numbers are at most 1 billion.

输出格式

* Line 1: The smallest cost of a photograph containing each distinct breed ID.

样例 #1

样例输入 #1

1
2
3
4
5
6
7
6 
25 7 
26 1 
15 1 
22 3 
20 1 
30 1

样例输出 #1

1
4

提示

There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.

The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//滑动窗口思想
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll sum;
ll n;
const int N=1e5+10;
struct node
{
ll x;
ll bianhao;
}s[N];
ll z;
bool cmp(node g,node y)
{
	return g.x<y.x;	
}
map<int ,int>t;
map<int ,bool>q;
ll ans=1e13;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i].x>>s[i].bianhao ;
		if(!q[s[i].bianhao])
		{
			q[s[i].bianhao]=1;
			sum++;
		}
	}
    //记录一下编号，和所有编号（去重）个数
sort(s+1,s+1+n,cmp);
    //排序，按照坐标
t[s[1].bianhao]=1;
z=1;
int tail=1;
for(int i=1;i<=n;i++)
{
	while(z<sum&&tail<n)
	{
		tail++;
		t[s[tail].bianhao]++;
		if(t[s[tail].bianhao]==1)
		{
			z++;
		}		
	}
		if(z==sum)
		{
			ans=min(ans,s[tail].x-s[i].x);
		}
		t[s[i].bianhao]--;
		if(t[s[i].bianhao]==0)
		{
			z--;
		}	
	}	
cout<<ans;	
}

天际线

题目描述

Latium 省的 Genoa 是亚平宁半岛西海岸北端的一片土地，自然资源丰富，却无人居住。你受到罗马执政官 Caesar 的委任，前往 Genoa 建立新的城市。Caesar 对这次任务的要求是在 Genoa 这片土地上建立起一座繁荣的城市，他将以此作为衡量你的表现的标准。

正在你大刀阔斧地进行城市建设的时候，Caesar 突然写信给你，说他要检查 Genoa 的建设情况。Caesar 希望知道你的城市是什么样子，但是他又非常的忙，所以他只要你描述一下城市的轮廓就可以了，他将依照城市的轮廓决定你的薪水。

怎样描述一个城市的轮廓呢？我们知道 Genoa 所有的建筑共享一个地面，你可以认为它是水平的。所有的建筑用一个三元组 \((L_i,H_i,R_i)\)，其中 \(L_i\) 和 \(R_i\) 分别是建筑的左坐标和右坐标，\(H_i\) 就是建筑的高度。在下方所示的图表中左边建筑物描述如下 \((1,11,5)\)，\((2,6,7)\)，\((3,13,9)\)，\((12,7,16)\)，\((14,3,25)\)，\((19,18,22)\)，\((23,13,29)\)，\((24,4,28)\)，右边用轮廓线的顺序\((1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)\) 表示：

![]/images/oe7wpwsi.png)

输入格式

在输入数据中，你将得到一系列表示建筑的三元组。在输入数据中所有建筑的坐标中的数值都是小于 \(10000\) 的正整数，且至少有 \(1\) 幢建筑，最多有 \(5000\) 幢建筑。在输入输入中每幢建筑的三元组各占一行。三元组中的所有整数应由一个或多个空格分开。

输出格式

在输出数据中，你被要求给出城市的轮廓线。你可以这样来描述：对于所有轮廓线上的折点，按顺序排好，第奇数个点输出 \(x\) 坐标，第偶数个点输出 \(y\) 坐标，两个数之间用空格分开。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

样例输出 #1

1
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
int ans[10001], ls = 0x7f7f7f, rs = -0x7f7f7f;
int main() 
{
	std::ios::sync_with_stdio(false);
	int l, r, h;
	memset(ans, 0, sizeof(ans));
	while (cin >> l >> h >> r)
    //输入三个数据
    {
        //记录最左，最右
		ls = min(l, ls); rs = max(r, rs);
		for (int i = l; i < r; i++) 
		{
			if (ans[i] < h) ans[i] = h;
            //记录横坐标对应的最大高度
		}
	}
    //从左到右
	for (int i = ls; i < rs; i++) 
	{
		if (ans[i] != ans[i - 1]) 
            //如果和前面不相等
		{
				cout << i << " " << ans[i] << " ";
            //直接输出
		}
	}
	cout << rs << " " << 0 << '\n';
}

[USACO18OPEN] Out of Sorts G

题目描述

留意着农场之外的长期职业生涯的可能性，奶牛Bessie开始在不同的在线编程网站上学习算法。

她到目前为止最喜欢的算法是“冒泡排序”。这是Bessie最初的对长度为\(N\)的数组\(A\)进行排序的奶牛码实现。

1
2
3
4
5
6
7
8
sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

显然，奶牛码中的“moo”指令的作用只是输出“moo”。奇怪的是，Bessie看上去执着于在她的代码中的不同位置使用这个语句。

在用若干个数组测试了她的代码之后，Bessie得到一个有趣的观察现象：大的元素很快就会被拉到数组末尾，然而小的元素需要很长时间“冒泡”到数组的开头（她怀疑这就是为什么这个算法得名的原因）。为了实验和缓解这一问题，Bessie试着修改了她的代码，使代码在每次循环中向前再向后各扫描一次，从而无论是大的元素还是小的元素在每一次循环中都有机会被拉较长的一段距离。她的代码现在是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

给定一个输入数组，请预测Bessie修改后的代码会输出多少次“moo”。

输入格式

输入的第一行包含\(N\)（\(1 \leq N \leq 100,000\)）。接下来\(N\)行描述了\(A[0] \ldots A[N-1]\)，每个数都是一个范围为\(0 \ldots 10^9\)的整数。输入数据不保证各不相同。

输出格式

输出“moo”被输出的次数。

样例 #1

样例输入 #1

1
2
3
4
5
6
5
1
8
5
3
2

样例输出 #1

1
2

提示

供题：Brian Dean

这个题目不太理解（）

冒泡排序，通过交换相邻两数最终使得数组有序；

　　对于每个位置 i ，如果比 i 大的数都交换到 i 位置之后，比 i 小的数都交换到 i 位置之前；

　　那么，等结束最后一个 i 位置的时候，冒泡排序也就结束了，此时数组也就是有序的。

　　因此，对于此题的双向循环，每次判断当前位置 i 需要通过多少次while( )循环才能使得：

　　比 i 大的数都交换到 i 位置之后，比 i 小的数都交换到 i 位置之前；

　　因此，只需要求出 [1,i] 位置上比 i 大的数的个数，输出最大的那个即是答案；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# include <iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int c[N], n;
struct rec { int x, id; }a[N];
bool cmp(rec a, rec b)
{
    if (a.x != b.x) 
        return a.x < b.x;
    return a.id < b.id;
}
void update(int x)
{ 
    for (; x <= n; x += x & -x) 
        c[x]++; 
}
int query(int x) 
{ 
    int ret = 0; 
    for (; x; x -= x & -x) 
        ret += c[x]; 
    return ret; 
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin>>a[i].x, a[i].id = i;
    sort(a + 1, a + 1 + n, cmp);
    int ans = 1;
    for (int i = 1; i <= n; i++) 
    {
        update(a[i].id);
        ans = max(ans, i - query(i));
    }
    cout << ans;
    return 0;
}

[CEOI1999] Parity Game

题目描述

Alice 和 Bob 在玩一个游戏：他写一个由 \(0\) 和 \(1\) 组成的序列。Alice 选其中的一段（比如第 \(3\) 位到第 \(5\) 位），问他这段里面有奇数个 \(1\) 还是偶数个 \(1\)。Bob 回答你的问题，然后 Alice 继续问。Alice 要检查 Bob 的答案，指出在 Bob 的第几个回答一定有问题。有问题的意思就是存在一个 \(01\) 序列满足这个回答前的所有回答，而且不存在序列满足这个回答前的所有回答及这个回答。

输入格式

第 \(1\) 行一个整数 \(n\)，是这个 \(01\) 序列的长度。

第 \(2\) 行一个整数 \(m\)，是问题和答案的个数。

第 \(3\) 行开始是问题和答案，每行先有两个整数，表示你询问的段的开始位置和结束位置。然后是 Bob 的回答。odd表示有奇数个 \(1\)，even 表示有偶数个 \(1\)。

输出格式

输出一行，一个数 \(x\)，表示存在一个 \(01\) 序列满足第 \(1\) 到第 \(x\) 个回答，但是不存在序列满足第 \(1\) 到第 \(x+1\) 个回答。如果所有回答都没问题，你就输出所有回答的个数。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

样例输出 #1

1
3

提示

对于 \(100\%\) 的数据，\(1 \le n \leq 10^9\)，\(m \leq 5 \times 10^3\)。

多说一句

如果是偶数，证明什么呢，x-1和y是同号的

如果是奇数，证明什么呢，x-1和y是异号的

然后对同号和异号进行种类并查集

种类并查集详见并查集一文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//种类并查集+离散化
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
const int N = 1e6;
int fa[N];
//并查集
inline int find(int x) {
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
	int dx = find(x);
	int dy = find(y);
	if (dx != dy)
	{
		fa[dx] = dy;
	}
}
struct shuzi
{
	int x, y, z;
}a[N];
int d[2*N];
int top;
int main()
{
	cin >> n >> m;
	string s;
	for (int i = 1; i <= m; i++)
	{
		cin >> a[i].x >> a[i].y;
		a[i].x--;
        //-1是利用了前缀和的思想
		d[++top] = a[i].x;
		d[++top] = a[i].y;
		cin >> s;
		if (s[0] == 'o')
		{
			a[i].z = 1;
		}
		//奇数
		else
		{
			a[i].z = 0;
		}
		//偶数
}
	sort(d + 1, d + 1 + top);
	int x = unique(d + 1, d + 1 + top) - d - 1;
	//记录去重后的长度
	for (int i = 1; i <= 2 * x; i++)
	{
		fa[i] = i;
		//并查集初始化
	}
	for (int i = 1; i <= m; i++)
	{
		a[i].x = lower_bound(d + 1, d + 1 + x, a[i].x) - d;
		a[i].y = lower_bound(d + 1, d + 1 +x, a[i].y) - d;
		if (a[i].z)
		{
			//奇数
			if (find(a[i].x) == find(a[i].y))
			{
				//如果两个数奇偶性相同
				cout << i - 1;
				return 0;
			}
			else
			{
				merge(a[i].x, a[i].y + x);
				merge(a[i].x + x, a[i].y);
			}
		}
		else
		{
			if (find(a[i].x) == find(a[i].y + x))
			{
				cout << i - 1;
				return 0;
			}
			else
			{
				merge(a[i].x, a[i].y );
				merge(a[i].x+x, a[i].y + x);
			}


		}
	}
	cout << m;
}