本文共 897 字，大约阅读时间需要 2 分钟。

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

for (i = 0; i
   
    > l >> r;        for (j = l - 1; j < r; j++)            t[j]++;    }
   

所以，可设置一个数组存储，由于从左往右加，为了避免重复相加，所以每次右端要自减避免下次重复相加。为了好理解，可以将代码展开写一写。行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]造成的多次相加，最好是展开自己动手写一写帮助理解，这也算一个避免计算超时的技巧吧！

for (i = 0; i
   
    > l >> r;        t[l - 1]++;        t[r]--;    }    for (i = 1; i
   

#include 
   
    #include 
    
     using namespace std;typedef long long ll;ll a[200010], t[200010], ans;int main(){    int n, q, l, r, i;    cin >> n >> q;    for (i = 0; i
     
      > a[i];    sort(a, a + n);    for (i = 0; i
      
       > l >> r;        t[l - 1]++;        t[r]--;    }    for (i = 1; i
      
     
    
   

转载地址：https://jianzhuwang.blog.csdn.net/article/details/45030535 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！