Codeforces Round #297 (Div. 2)

题目不难，访问次数越多的点让其权重越大即可。要累计每个点的访问次数，因为是区间，所以每次输入l，r，区间内的每个点都要增加一次。倘若利用for循环遍历相加，会出现超时Time limit exceeded on test的情况（如下图代码）

1 for (i = 0; i<q; i++)
2     {
3         cin >> l >> r;
4         for (j = l - 1; j < r; j++)
5             t[j]++;
6     }

所以，可设置一个数组存储，由于从左往右加，为了避免重复相加，所以每次右端要自减避免下次重复相加。为了好理解，可以将代码展开写一写。行4中的自减原因在于行7和行8的代码，举个例子比如说l=1,r=3若是第一次访问那么t[1]=t[2]=t[3]=1，即区间内的每个元素都只访问了一次。此时如果套用行7，8的代码就会发现t[1]=1,t[2]=t[1]+t[2]=2,t[3]=t[2]+t[3]=3,所以每次输入l，r，都要t[r]--，避免下边t[i] += t[i - 1]造成的多次相加，最好是展开自己动手写一写帮助理解，这也算一个避免计算超时的技巧吧！

1 for (i = 0; i<q; i++)
2     {
3         cin >> l >> r;
4         t[l - 1]++;
5         t[r]--;
6     }
7     for (i = 1; i<n; i++)
8         t[i] += t[i - 1];

完整代码如下

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 ll a[200010], t[200010], ans;
 6 int main()
 7 {
 8     int n, q, l, r, i;
 9     cin >> n >> q;
10     for (i = 0; i<n; i++)
11         cin >> a[i];
12     sort(a, a + n);
13     for (i = 0; i<q; i++)
14     {
15         cin >> l >> r;
16         t[l - 1]++;
17         t[r]--;
18     }
19     for (i = 1; i<n; i++)
20         t[i] += t[i - 1];
21     sort(t, t + n);
22     for (i = 0; i<n; i++)
23         ans += a[i] * t[i];
24     cout << ans<< endl;
25     return 0;
26 }