The only difference between easy and hard versions is constraints.

Now elections are held in Berland and you want to win them. More precisely, you want everyone to vote for you.

There are 𝑛 voters, and two ways to convince each of them to vote for you. The first way to convince the 𝑖-th voter is to pay him 𝑝𝑖 coins. The second way is to make 𝑚𝑖 other voters vote for you, and the 𝑖-th voter will vote for free.

Moreover, the process of such voting takes place in several steps. For example, if there are five voters with 𝑚1=1, 𝑚2=2, 𝑚3=2, 𝑚4=4, 𝑚5=5, then you can buy the vote of the fifth voter, and eventually everyone will vote for you. Set of people voting for you will change as follows: 5→1,5→1,2,3,5→1,2,3,4,5.

Calculate the minimum number of coins you have to spend so that everyone votes for you.

链接🔗

「CodeForces 1251E2」Voting

题解

代码很好理解～

代码

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int maxd = 2e5+10;
vector<int> a[maxd];
priority_queue<int,vector<int>,greater<int> > que;
int b[maxd];
int main()
{
//    freopen("a.in","r",stdin);
//    freopen("k.out","w",stdout);
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;scanf("%d",&n);
        for(int i=0;i<n;i++) a[i].clear();
        for(int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            a[x].push_back(y);
        }
        int now = 0;
        for(int i=0;i<n;i++)
        {
            b[i] = max(0,i-now);
            now += a[i].size();
            //printf("%d %d\n",i,b[i]);
        }

        now = 0;
        long long ans = 0ll;
        for(int i=n-1;i>=0;i--)
        {
            for(int x:a[i]) que.push(x);
            while(now < b[i])
            {
                ans += que.top(); que.pop();
                now++;
            }
        }
        while(!que.empty()) que.pop();
        printf("%lld\n",ans);
    }
    return 0;
}