“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 F-排列计算

根据题目意思可以得知，按照某个数字被加的次数排序，然后从大往小乘即可。
那么，问题转化为两个部分：1、区间修改+单点查询
2、排序
看数据范围：n 对应 2E5 m 对应 2E5，开线段树，维护和值，进行区间更新，复杂度 nlogn
然后，单点查询所有点的值，复杂度 nlogn
之后，排序，复杂度 nlogn
最后，循环求和输出，复杂度 n
可以得知，复杂度 O(nlogn)，问题可以解决。

注：我没有用排序，直接使用降序优先队列，复杂度nlogn，AC代码如下：

#include<bits/stdc++.h>
#define MAXN 200010              //今天RE了一次，就是因为平时习惯1E5 + 5，没注意到本题的 2E5 
#define inf 0x3f3f3f3f  

using namespace std;  

priority_queue <int,vector<int>,less<int> > q;

struct node{  
    int l,r;//区间[l,r]  
    int add;//区间的延时标记  
    int sum;//区间和  
}tree[MAXN<<2];//一定要开到4倍多的空间  

void pushup(int index){  
    tree[index].sum = tree[index<<1].sum+tree[index<<1|1].sum;  

}

void pushdown(int index){   
    if(tree[index].add){  
        tree[index<<1].sum += (tree[index<<1].r-tree[index<<1].l+1)*tree[index].add;  
        tree[index<<1|1].sum +=(tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].add;    
        tree[index<<1].add += tree[index].add;  
        tree[index<<1|1].add += tree[index].add;  
        tree[index].add = 0;  

    }  
}  

void build(int l,int r,int index){  
    tree[index].l = l;  
    tree[index].r = r;  
    tree[index].add = 0;//刚开始一定要清0  
    if(l == r){  
        tree[index].sum = 0;  
        return ;  
    }  
    int mid = (l+r)>>1;  
    build(l,mid,index<<1);  
    build(mid+1,r,index<<1|1);  
    pushup(index);  
}  

void updata(int l,int r,int index,int val){  
    if(l <= tree[index].l && r >= tree[index].r){    
        tree[index].sum += (tree[index].r-tree[index].l+1)*val;  

        tree[index].add += val;//延时标记  
        return ;  
    }  
    pushdown(index);  
    int mid = (tree[index].l+tree[index].r)>>1;  
    if(l <= mid){  
        updata(l,r,index<<1,val);  
    }  
    if(r > mid){  
        updata(l,r,index<<1|1,val);  
    }  
    pushup(index);  
}  

int query(int l,int r,int index){  
    if(l <= tree[index].l && r >= tree[index].r){  
        return tree[index].sum;  
    }  
    pushdown(index);  
    int mid = (tree[index].l+tree[index].r)>>1;  
    int ans = 0;  
    int Max = 0;  
    int Min = inf;  
    if(l <= mid){  
        ans += query(l,r,index<<1);   
    }  
    if(r > mid){  
        ans += query(l,r,index<<1|1);   
    }  
    return ans;   
}  

int main()  
{  
    int n,m;  
    scanf("%d%d",&n,&m);
    build(1,n,1);                //建树时全部给0
    for(int i = 0;i < m;i++){
        int l,r;
        cin>>l>>r;
        updata(l,r,1,1);
    }
    for(int i = 1;i <= n;i++){
    int r = query(i,i,1);
    q.push(r);
    }
    long long ans = 0;
    long long r1 = n;
    while(!q.empty()){
    long long t = q.top();
    ans += t * r1--;
    q.pop();
    if(t == 0) break;            //一个很小的优化
    }
    cout<<ans<<endl;
    return 0;  
}

如有意见建议，欢迎联系2339814485（QQ），注明来意即可。