线段树

线段树

#include<bits/stdc++.h>
using namespace std;
long long ans=0;
vector<long long> sort(vector<long long> &a,vector<long long> &b){
    int n1=a.size();
    int n2=b.size();
    vector<long long> res;
    int i=0,j=0;
    while(i<n1&&j<n2){
        if(a[i]<=b[j]){
            res.push_back(a[i]);
            i++;
        }
        else{
            res.push_back(b[j]);
            j++;
            ans+=n1-i;
        }
    }
    while(i<n1){
        res.push_back(a[i]);
        i++;
    }
    while(j<n2){
        res.push_back(b[j]);
        j++;
    }
    return res;
}
namespace SegTree{   //线段树
    vector<vector<long long>> t(800001);
    vector<vector<long long>> a(100001);
    void build(int R,int l,int r){
        if(l==r){
            t[R]=a[l];
            return;
        }
        int mid=l+r>>1;
        build(R<<1,l,mid);
        build(R<<1|1,mid+1,r);
        t[R]=sort(t[R<<1],t[R<<1|1]);
    }
}
class Solution {
public:
    /**
     * 求解合法的(i,j)对的数量
     * @param n int整型 n个人
     * @param m int整型 m个窗口
     * @param a int整型vector 长度为n的vector,顺序表示1-n号客人的办理业务所需时间
     * @return long长整型
     */
    long long getNumValidPairs(int n, int m, vector<int>& a) {
        priority_queue<long long, vector<long long>,greater<long long>> q;
        for(int i=0;i<m;i++) q.push(0);
        vector<long long> rec;
        for(int i=0;i<n;i++){
            long long curr = q.top();
            q.pop();
            curr+=a[i];
            rec.push_back(curr);
            q.push(curr);
        }
        for(int i=0;i<n;i++)  
            SegTree::a[i]=vector<long long>{rec[i]};
        SegTree::build(1,0,n-1);  
        int rr = ans;
        return ans;
    }
};