众所周知，唐老师特别喜欢挑战难度很高的电子游戏，有一天他挑战了一款回合对战游戏，唐老师的阵地有N个哨塔，编号由1到N，且初始时每个哨塔有自己的血量，游戏开始后，敌军会对唐老师的阵地发起M轮进攻，每轮进攻都会对一些哨塔产生等量的伤害。且满足第i轮进攻会对编号Li到Ri的哨塔造成等量伤害Di，M轮进攻结束后，唐老师需要快速对血量最低的K座哨塔进行修补，若存在与第K座哨塔相同血量仍需要输出，输出的哨塔编号个数可能多余K个，由于哨塔特别多，所以请帮忙设计程序帮助唐老师快速的找出需要修补的哨塔的编号，输出编号按从小到大顺序。

输入格式：
第一行包含两个三整数N,M,K。
第二行包含N个正整数，表示编号1到N哨塔的血量。
接下来M行，每行包含三个整数L，R，D，表示一轮进攻对编号L到R的哨塔造成了D点伤害。
输出格式：
共一行，包含K个正整数，以空格分隔，表示需要修补的哨塔编号。

数据范围：
1≤N,M≤100000,
1≤L≤R≤N,
1≤K≤N,
1≤D≤1000,
1≤哨塔血量≤21亿,且M轮进攻后不存在哨塔血量小于等于0的情况。

输入样例：
7 3 6
500 500 500 500 500 500 500
1 7 100
2 3 50
3 5 200
输出样例：
1 2 3 4 5 6 7

#include<iostream>
using namespace std;
const int N = 100010;

typedef struct Tower
{
    int idx;
    int hp;
}tower;

tower a[N];
int d[N];
bool ans[N];

inline void insert(int l,int r,int c)
{
    d[l]+=c;
    d[r+1]-=c;
}

int part(tower q[],int l,int r,int k)
{
    if(l == r) return q[l].hp;
    int key = q[l+r>>1].hp;
    int i=l-1,j=r+1;
    while (i < j)
    {
        do i++; while(q[i].hp<key);
        do j--; while(q[j].hp>key);
        if (i < j)
            swap(q[i],q[j]);
    }
    int llen = j-l+1;
    if( k<=llen)
        part(q,l,j,k);
    else
        part(q,j+1,r,k-llen);


}


int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) 
    {
        a[i].idx = i;
        scanf("%d",&a[i].hp);
        insert(i,i,a[i].hp);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,d;
        scanf("%d%d%d",&l,&r,&d);
        insert(l,r,-d);
    }
    for(int i=1;i<=n;i++){
        a[i].hp = a[i-1].hp+d[i];
        //printf("%d ",a[i].hp);
    }
    //printf("\n");
    int khp = part(a,1,n,k);
    for(int i=1;i<=n;i++)
        if (a[i].hp <= khp)
            ans[a[i].idx] = true;
    for(int i=1;i<=n;i++)
        if(ans[i]) 
            printf("%d ",i);

    return 0;

}

暂时没有制作非常准确大数据，不能完全确定代码的正确性，如果有感兴趣的同学，可以自行研究一下~

作者：抱元守一
链接：https://www.acwing.com/activity/content/code/content/593593/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。