西南民族大学第十届校赛（网络赛）题解

题目比较简单。

A.dreamstart的催促

• 思路
• 题目描述
• 代码

裸的快速幂。注意long long

题目连接

描述

有一天集训队的学弟们正在计算一堆数，但是dreamstart感觉他们算的太慢了，就让他们坐在一起想出一个快速计算的方法，但是由于他们一时想不出来，想让你帮助他们。他们说现在有一个数列，要算出第 i 个数的 i 次幂并且把每个数计算出来的值加到一起，最后答案模10000019。

聪明的你可以帮助他们吗？

输入

第一行有一个整数n，n <= 1e5

接下来一行有n个数，每个数的大小不超过1e16

输出

输出取模之后的和

样例输入

4
1 6 9 12

样例输出

21502

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;
const int Mod=10000019;
typedef long long ll;
 
ll Qpow(ll x,ll n){
    ll ans=1ll;
    while(n){
        if(n&1) ans=(ans*x)%Mod;
        x=(x*x)%Mod;
        n>>=1;
    }
    return ans;
}
 
 
int main()
{
    ll n,x,ans=0;
    scanf("%lld",&n);
    rep(i,0,n){
        scanf("%lld",&x);
        ans=(ans+Qpow(x,i+1))%Mod;
    }
    printf("%lld\n",ans);
    return 0;
}

---

B.TRDD got lost again

• 思路
• 题目描述
• 代码

处理一下就是BFS裸题，把门看成一个格子，最后路径长度/2.

题目连接

描述

X城市是一个交通十分不便利的城市，城市可以看成一个n m大小的矩阵， 现在TRDD手里有该城市的地图:一个2n+1行, 2 *m+1列大小的地图。现在TRDD所在的格子用S表示,机场所在的格子用T表示。 其他格子用空格表示，地图上左右相邻的两个格子如果不能通行用”|”表示， 上下相邻的两个点如果不能通行用”-“表示，”+“表示格子的四个角。 题目保证城市X最外圈无法通行（具体请看样例输入）。
为了能尽快赶到机场，TRDD想请你帮忙计算出他到达机场最少需要走过多少个格子（包括起点S和终点T）。
如果无法到达机场T，则输出”TRDD Got lost…TAT”(不包括双引号)。

输入

第一行读入两个数n, m（1 <= n, m <= 3000)表示X城市的大小。

之后有2 n + 1行， 每行有2 m + 1个字符， 用来表示TRDD手里的地图

题目保证S和T都有且仅有一个。

输出

如果TRDD能到达机场， 则输出TRDD最少需要经过几个格子
否则输出”TRDD Got lost…TAT”(不包括双引号)

样例输入

4 3
+-+-+-+
|S| | |
+ +-+-+
| | | |
+ +-+-+
| |T  |
+ +-+ +
|     |
+-+-+-+
3 3
+-+-+-+
|S|   |
+ + +-+
| | |T|
+ + +-+
|   | |
+-+-+-+

样例输出

8
TRDD Got lost...TAT

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=6e3+5;
char Map[N][N];
int n,m,Sx,Sy,Ex,Ey;char x,y;

int M_x[4]={1,0,-1,0},
    M_y[4]={0,1,0,-1};

struct node{int x,y,step;};


void bfs(){
    queue<node> Q;
    Q.push((node{Sx,Sy,1}));
    while(!Q.empty()){
        node tem=Q.front();
        rep(i,0,4){
            int X=tem.x+M_x[i];
            int Y=tem.y+M_y[i];

            if(Map[X][Y]=='*') continue;
            
            if(Map[X][Y]=='T') {
                  printf("%d\n",tem.step/2+1);
                  return;
            }
            
            Map[X][Y]='*';
            Q.push(node{X,Y,tem.step+1});
        }
        Q.pop();
    }
    printf("TRDD Got lost...TAT\n");
    return;
}

int main()
{
    scanf("%d%d",&n,&m);
    getchar();
    CRL(Map,'*');
    rep(i,0,n*2+1){
        rep(j,0,m*2+1){
           x=getchar();
           if(x==' '||x=='T') Map[i][j]=x;
           else if(x=='-'||x=='|') Map[i][j]='*';
           else if(x=='S'){
                Map[i][j]=' ';
                Sx=i;
                Sy=j;
           }
        }
        getchar();
    }

    bfs();
    return 0;
}

---

C.Company

• 思路
• 题目描述
• 代码

dfs

题目连接

描述

在一个偏僻的大山里， 一共有n个村庄， 编号1~n，每个村庄都有一定数量的村民， 其中只有1号村庄有水井，为了方便村民们日常用水，村民们一共修建了n-1根水管， 保证每一村庄都能有水喝。因为水是从高流向低， 所以我们知道1号村庄海拔最高， 与1号村庄直接相连的村庄高度次之， 以此类推。

对于每一个村庄， 如果这个村庄的村民人数<=k, 我们称之为”劳动力不足的村庄”。
现在我们想知道， 如果水井不修在1号村庄， 而是修在任意一个村庄， 那么有水流过的村庄中有多少个村庄是”劳动力不足的村庄”（包括有水井的村庄本身）。

输入

第一行输入两个数n(1 <= n <= 200000)村庄的数量， 以及劳动力的评估标准k(1 <= k <= 1e9)
第二行有n个数， 表示这n个村庄的村民数(1 <= a <= 1e9)
之后有n-1行， 每行两个数字u, v（1 <= u, v <= n) u, v两个村庄之间有一条水管。

输出

输出n个数， 输出假设水井修在第i(1 <= i <= n)个村庄，那么有水流过的村庄中有多少个村庄是”劳动力不足的村庄”。

两个数之间用空格隔开

样例输入

8 10
12 15 11 4 5 19 14 20
3 7
1 5
2 1
6 5
2 3
6 4
8 3

样例输出

2 0 0 1 2 1 0 0

#include<stdio.h>
#include<string.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
#define lowbit(x) (x&(-x))
const int N=1e6+5;

struct edge {int To,next;}Edge[N];  //链式前向星存图
int cnt=-1,Begin[N],a[N]={0};

void add(int a,int b){
    Edge[++cnt]=(edge{b,Begin[a]});
    Begin[a]=cnt;
}

int dfs(int x,int f){       //求子树和
    int tem=a[x];
    for(int i=Begin[x];~i;i=Edge[i].next)
        if(Edge[i].To!=f)
            tem+=dfs(Edge[i].To,x);
    return a[x]=tem;
}

int main()
{
    int s,e,n,k;
    scanf("%d%d",&n,&k);
    CRL(Begin,-1);
    rep(i,1,n+1){
        scanf("%d",&a[i]);
        a[i]= a[i]<=k;
    }

    rep(i,1,n){
        scanf("%d%d",&s,&e);
        add(s,e);
        add(e,s);
    }
    dfs(1,-1);
    rep(i,1,n+1) printf("%d%c",a[i]," \n"[i==n]);
    return 0;
}

---

D.>A->B->C-

• 思路
• 题目描述
• 代码

对于A，就看A喜欢的喜欢的喜欢的人是不是A。

题目连接

描述

一天小A在金色的银杏树下向他喜欢的小姐姐B表白了，“对不起，我喜欢的是C”，B这样说道，小A尴尬的笑了笑转身离开了。他心里默默说着“对不起，C喜欢我。”(233333333)
Love triangle被定义为：如果A喜欢B，B喜欢C，C喜欢A则称为Love triangle。现在让你寻找有没有Love triangle。

输入

第一行一个正整数N(n<=5000)，第二行n个数$X_1，X_2，X_3……X_n$代表i喜欢$X_i$。

输出

如果存在Love triangle则输出YES，没有则输出NO。

样例输入

5
2 4 5 1 3

样例输出

YES

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=5e3+5;
int a[N]={0};

int main()
{
    int n,Flag=0;
    scanf("%d",&n);
    rep(i,1,n+1){
        scanf("%d",&a[i]);
        if(a[a[a[i]]]==i) Flag=1;   // i喜欢的喜欢的喜欢的人是不是i
    }

    puts(Flag? "YES":"NO");
    return 0;
}

---

E.PPY的字符串

• 思路
• 题目描述
• 代码

字符串模拟

题目连接

描述

Siry特别喜欢数学， 在他很小的时候他就对数字特别感兴趣， 他喜欢念数字。
具体念法是这样的： 给你一个数字， 依次念出每个数字有几个相邻（Siry会大声说出a个b, c个d…）， 组合起来形成一个新的数字。
如：
2331的念法就是1个2,2个3,1个1， 形成的新数字就是122311。 再念一次就是1个1,2个2,1个3, 2个1, 形成的数字是11221321。
现在Siry大声的念出了第一次的数字x， Siry总共想要念n次， 你能快速的知道第n次的数字是多少吗？

输入

每行输入两个数字x，n。
1≤ x≤ 109,1≤ n≤ 30

输出

输出一行，包括第n个数字的位数和这个数字。 位数和数字之间用空格隔开。

样例输入

222 2

样例输出

2 32

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
#define LL long long

void add(int x,string &s){
    if(x) add(x/10,s);
    else return;
    s+=char('0'+x%10);
}

string change(string s){
    string s1="";
    int num,i=0;char c;
    while(i<s.size()){
        num=0;c=s[i];
        while(i<s.size()&&s[i]==c){
            i++;num++;
        }

        add(num,s1);
        s1+=c;
    }
    return s1;
}

int main() {
    string s;int n;
    cin>>s>>n;
    n--;
    while(n--) s=change(s);

    cout<<s.size()<<" "<<s<<endl;
    return 0;
}

---

F.集训队脱单大法：这是一道只能由学姐我自己出数据的水题

• 思路
• 题目描述
• 代码

思维题。
很明显，无论怎么分，整个数列最大值一定是一个对的最大值。
分两种情况讨论：

• 最大值被分到了前面一个组，那么无论怎么分，后面的那个组的最大值 $x$ 一定 $x<=a[n]$ ,那么很明显当 $x==a[n]$ 时，有最优解，此时只有把a[n]单独分成一组。
• 最大值被分到了后面一个组一样的，当 $x==a[1]$ 时，有最优解;

然后答案就是

$$ans = Max-min(a[1],a[n])$$

题目连接

描述

总所不周知！ZZZZone有了女朋友却谁也不知道。但是ZZZZone在集训队总是和陈大佬走的很近，每天搂搂抱抱十分不成体统！于是就被ZZZZone的女朋友给知道了，但是呢，ZZZZone的女朋友是一个热爱画画的温柔又可爱的女子，于是她决定把ZZZZone大卸两块，没错是两块！！

ZZZZone呢他的长度为 n，并且每个单位长度都有一个相对应的重量，他的小女朋友希望将ZZZZone切成两部分后，两个部分中的最大重量之差的绝对值最大（显然两个部分均不能为空啊），她呢觉得很惆怅，不知道该怎么切最好，所以想让你们来想想办法。

输入

第一行为一个$n\（2 <= n <= 10^5）$，表示ZZZZone的长度，第二行为n个数，表示ZZZZone每个单位长度的重量（$0 <= a[i] <= 10^6$）。

输出

输出切成两部分后，每部分的重量的最大值之差的绝对值最大是多少。

样例输入

4
3 4 1 6

样例输出

3

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;

int main(){
    int Star,n,Max=0,x;
    scanf("%d%d",&n,&Star);
    Max=Star;

    for(int i=1;i<n;i++){
        scanf("%d",&x);
        Max=max(Max,x);
    }

    printf("%d\n",Max-min(Star,x));

    return 0;
}

---

G.不想再WA了

• 思路
• 题目描述
• 代码

把A,C,W看看成0,1,2，这样就是三进制数里面不要31.
很明显的数位DP.

题目连接

描述

欢迎参加西南民族大学 2018 年校赛。
对于你来说，做题 WA 了 是一件很痛苦的事，所以你从现在开始不想再看到有题 WA 了。
那么现在给你 A，C，W 三种字符，问组成一个长度为 n（不含 WA，即 W 后一个字符不能为 A ) 的字符串，总共有多少种方案？( T 组数据)

输入

先输入一个 T，表示有 T 组数据。
然后输入需要组成字符串的长度 $n_i$ $(1 <= i <= T)$
$1 <= T <= 10$
$1 <= n_i <= 10$

输出

对于每个 $n_i$ 输出对应的答案

样例输入

2
1
2

样例输出

3
8

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;
const int maxn=100;
typedef long long ll;

int a[20];
int dp[20][5];
ll dfs(int pos,int pre,int sta,bool limit){
    if(pos==-1) return 1;
    if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
    int up=limit ? a[pos] : 2;
    ll tmp=0;
    for(int i=0;i<=up;i++){
        if(pre==2 && i==0)continue;
        tmp+=dfs(pos-1,i,i==2,limit && i==a[pos]);
    }
    if(!limit) dp[pos][sta]=tmp;
    return tmp;
}

ll solve(int n){
    int pos=0;
    rep(i,0,n) a[i]=2;

    return dfs(n,-1,0,true);
}

int main()
{
    int n,T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(dp,-1,sizeof dp);
        printf("%d\n",solve(n));
    }
    return 0;
}

---

H.Ricky’s RealDan’s Ricky

• 思路
• 题目描述
• 代码

博弈题。我们可以发现Ricky不能改变奇偶性而RealDan可以（奇数拿掉奇数变偶数）。所以RealDan可以视情况留下奇数或偶数，所以除了只有一堆偶数的情况，都是RealDan赢。

题目连接

描述

The 2019 is coming！Ricky 和 RealDan为了庆祝2018一年的成果，准备去大吃一顿，然而 Ricky 想吃火锅， RealDan 想吃海鲜。为了解决吃什么的难题， 他们向聪明的神秘人（出题人）寻求帮助，神秘人则给他们出了这样一个问题：
现在有 n 个娃娃机，第i(1 <= i <= n) 个娃娃机中有 a[i] 个娃娃。
规则如下：

• Ricky 和 RealDan 轮流抓娃娃，
• Ricky 每轮只能从其中一个娃娃机中抓走偶数个娃娃。
• RealDan 每轮只能从其中一个娃娃机中抓走奇数个娃娃。
• 每人每轮至少抓走一个娃娃（他们都超级厉害）, Ricky 先开始抓。

他们在神秘人的教导下，都已经变得非常聪明。最后谁抓不了娃娃，谁就被视为 loser，并且还要把自己抓到的娃娃送给对方，loser也必须去Winner喜欢的地方吃饭。

现在他们找到你，想让你看一下他们究竟谁可以赢。
Note: All the best wishes give Ricky and RealDan by their old friend ~

输入

第一行一个t，表示t组数据。
每组数据有两行：
第一行一个n（1 <= n <= 100000）代表n个娃娃机
下一行有n个数字，代表每一个娃娃机中的娃娃数量a[i] (1 <= a[i] <= 1e9)

输出

如果最后Ricky获胜，则输出“Ricky is Winner”(不包括双引号)，反之则输出“RealDan is Winner”(不包括双引号)。

样例输入

1
2
1 2

样例输出

RealDan is Winner

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;
 
int main()
{
    int T,n,x;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        rep(i,0,n) scanf("%d",&x);

        if(n==1&&(x%2==0)) puts("Ricky is Winner");
        else puts("RealDan is Winner");
    }
 
    return 0;
}

---

I.小A的期末作业

• 思路
• 题目描述
• 代码

模拟

题目连接

描述

期末了， 老师给小A布置了一道期末作业， 让小A设计一个图案， 追求完美的小A想要用编程来完成这个图案：
小A想要设计一个由符号组成的“大于号”图案， 图案的大小为n， 一共有2n-1行， 每行有n个符号， 每一行前面有一些空格。
第一行没有空格， 第二行有一个空格， 第三行有两个空格。。。。 依次类推
图案是轴对称图形。

输入

读入一个数字n(1 <= n <= 100)， 表示图案的大小.

输出

输出小A想要的图形

样例输入

4

样例输出

****
 ****
  ****
   ****
  ****
 ****
****

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;

int main()
{
    int n;
    scanf("%d",&n);
    rep(i,0,n){
        rep(j,0,i+n) putchar(j<i? ' ':'*');
        printf("\n");
    }

    repd(i,0,n-1){
        rep(j,0,i+n) putchar(j<i? ' ':'*');
        printf("\n");
    }

    return 0;
}

---

J.怪盗基德 & 月之瞳宝石

• 思路
• 题目描述
• 代码

二分。
对于每一个星体，在能源体中二分找离他最近的。

题目连接

描述

在这片寂静的夜色之下，他就这样静静的降临在我的面前，他的眼神就好像能看透了一切，露出了无所畏惧的笑容。一袭白斗篷和一顶白礼帽，不带一丝多余的动作，他的脸在单眼眼睛跟逆光之下。

to 世纪末的魔术师
By the mysterious man

怪盗基德在上次失败后，对美丽的月之瞳宝石非常觊觎，他想要得到它，以世纪末的魔术师的名义。但是却遇到了重重机关阻拦，眼看到了月之瞳宝石盒之前，怪盗基德却停下了脚步。

“世界上有些谜，还是让它永远成为谜比较好”

话音刚落，只见一片白雾，待雾散开之时，他已经消失在月色之中。

在怪盗基德走后，你潜入进去，却发现，上面篆刻着一段奇怪的话：

在缥缈的宇宙中，有一条穿越时空的隧道，在这条隧道中，有着许多星体和能源体，他们都排列在一条直线上，对于每个星体而言，他们都需要能源体的照耀才能够存活于这条时空隧道当中，当然一个能源体可以同时为多个星体提供能源（对于一个能源体来说，也可能没有星体需要它提供能源）。但是，有所限制的是每个能源体只能为与自身相距x之内的星体提供能源。现在需要你找到最小的x，使得每个星体都能够得到能源(即每个星体必须得到至少一个能源体的照耀)。

现在是你作为怪盗基德的徒弟大展身手的时候了。

输入

输入共三行，第一行有两个数n和m(1 <= n, m <= 1e5)，分别代表有n个星体，m个能源体。

第二行有n个数a1, a2, … an，代表n个星体的位置。（-2e9 <= a[i] <= 2e9）

第三行有m个数b1, b2, … bm，代表m个能源体的位置。(-2e9 <= b[j] <= 2e9)

输出

输出最小的x，满足每个星体都有至少一个能源体为其提供能源。

样例输入

3 2
-2 2 4
-3 0

样例输出

4

#include<bits/stdc++.h>
using namespace std;
#define INIT(a,x) memset(a,x,sizeof(a))
#define LL long long
const LL mod=10000019;
LL a[100007]={0},b[100007]={0};
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    for(int i=0;i<m;i++)scanf("%lld",&b[i]);
    sort(a,a+n);sort(b,b+m);
    LL ans=-555555;
    for(int i=0;i<n;i++){
        LL *q=lower_bound(b,b+m,a[i]);
        LL tem;
        if(q==b)tem=abs(a[i]-*q);
        else if(*q<a[i])tem=abs(a[i]-*(q-1));
        else tem=min(abs(a[i]-*q),abs(a[i]-*(q-1)));
        ans=max(ans,tem);
    }
    printf("%lld\n",ans);
    return 0;
}

---

K.正方体

• 思路
• 题目描述
• 代码

模拟too

题目连接

描述

已知一个正方体，每个面上都有任意一个数（假设每一面的面积足够大来装下当前面上的数字），现被展开成了如下形式：

输入中保证第一行有一个面，第二行有四个面，第三行有一个面。请用代码检查这个正方体对立面上的数是否相同。

输入

输入包含多个测试样例。第一行为一个整数T（1 <= T <= 1e4）,接下来每个样例占3行，每行都包括4个数，为0表明当前位置不表示面，每个面上的数值范围不超过int。

Eg:上图的输入为：
0 1 0 0
2 4 2 4
0 0 1 0

输出

对于每个测试样例，如果当前正方体的三个对立面的数都分别相同的话就输出”Yes!”，否则输出”No!”。每个结果占一行，注意每50个结果要加一个空行。

样例输入

3
0 2 0 0
1 3 1 3
0 2 0 0
0 2 0 0
1 3 1 3
0 0 0 2
0 0 0 2
1 2 2 1
0 0 1 0

样例输出

Yes!
Yes!
No!

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;

int main()
{
    int a[5]={0},T,x,m,Flag=0,n;

    scanf("%d",&T);
    rep(_,1,T+1){
        Flag=0;
        rep(i,0,4) {scanf("%d",&x);if(x) n=x;}
        rep(i,0,4)  scanf("%d",&a[i]);
        rep(i,0,4) {scanf("%d",&x);if(x) m=x;}

        if(a[1]!=a[3]||a[0]!=a[2]) Flag=1;
        if(n!=m) Flag=1;
        
        puts(Flag? "No!":"Yes!");
        if(_%50==0) printf("\n");
    }

    return 0;
}

---

L.简单的分数

• 思路
• 题目描述
• 代码

先通分，加减完再处以分子分母的最大公约数。

题目连接

描述

John最近对分数很感兴趣，在研究分数的加减运算。现在要求计算两个分数的运算。

输入

输入一个正整数T，表示有T组数据
每组数据包括5个整数op，a，b，c，d
op为1表示a/b + c/d；op为0表示为a/b – c/d
其中1 <= T, a，b，c，d <= 100;

输出

输出分数运算结果“x/y”，要求x/y是最简分数。

样例输入

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

样例输出

5/6
0/1
1/1
-1/6

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;

int main()
{
    int n,op,a,b,c,d;
    scanf("%d",&n);

    rep(i,0,n){
        scanf("%d%d%d%d%d",&op,&a,&b,&c,&d);
        a*=d;c*=b;b*=d;d=b;

        if(op) a+=c;
        else a-=c;

        int gcd=__gcd(a,b);
        if(a<0||b<0) printf("-");
        printf("%d/%d\n",abs(a/gcd),abs(b/gcd));

    }
    return 0;
}

---

M.HJ浇花

• 思路
• 题目描述
• 代码

因为0 <= l <= r <= 10，所以可以直接差分。
用map存一下个数（ map<次数,盆数> ）。

题目连接

描述

HJ养了很多花（99999999999999999999999999999999999盆），并且喜欢把它们排成一排，编号0~99999999999999999999999999999999998,每天HJ都会给他的花浇水，但是他很奇怪，他会浇n(1 <= n <= 2 * 105)次水，每次都会选择一个区间[l, r]，(0 <= l <= r <= 106),表示对区间[l, r]的花都浇一次水。现在问你，通过这些操作之后，被浇了i(1 <= i <= n)次水的花的盆数。

输入

输入：第一行一个n，表示HJ的操作次数，接下来的n行，表示每一次选择的浇水区间。

输出

输出：输出n个数字Cnt1, Cnt2……Cntn,（用空格隔开）Cnti表示被浇了i次水的花的盆数。

样例输入

3
0 3
1 3
3 8
3
1 3
2 4
5 7

样例输出

6 2 1
5 2 0

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=2e6+5;
int a[N]={0};
map<int,int> M;
 
int main()
{
    int n,l,r,Max=0;
    scanf("%d",&n);
    rep(i,0,n){
        scanf("%d%d",&l,&r);
        a[l]++;
        a[r+1]--;
        if(r+1>Max) Max=r+1;
    }
    rep(i,1,Max+1) a[i]+=a[i-1];
    rep(i,0,Max+1) M[a[i]]++;
 
    map<int,int>::iterator iter=M.begin();
    rep(i,1,n+1) 
        printf("%d%c",M[i]," \n"[i==n]);
    
    return 0;
}

---