题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define N 300010
using namespace std;

typedef pair<int,int> PII;

PII add[N];   //+c操作的区间范围
PII ask[N];  //前缀和询问的区间范围
int s[N];  //存储输入坐标位置+c后的前缀和
vector<int> a; //存储+c操作和询问区间范围的坐标,最后a.size()就是计算要用到的坐标数量

int find(int x) //二分查找坐标x在a数组存储的位置+1，之后的+c操作就在S[x位置+1]处进行
{
    int l,r,mid;
    l=0;
    r=a.size()-1;
    while(l<r)
    {
        mid=(l+r)/2;
        if(x<=a[mid])
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    return r+1;
}

int main()
{
    int n,m,i,k,l,r,x,c;
    cin>>n>>m; //n次+c,m次前缀和
    for(i=0;i<n;i++)
    {
        cin>>x>>c; //x坐标，c加数
        add[i]=pair<int,int>(x,c);
        a.push_back(x);
    }

    for(i=0;i<m;i++)
    {
        cin>>l>>r;  //[l,r]区间左右端点
        ask[i]=pair<int,int>(l,r);
        a.push_back(l);
        a.push_back(r);
    }

    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end()); //删除坐标数组a中最后一个非重复元素之后的所有重复元素

    for(i=0;i<n;i++)  //+c操作
    {
        k=find(add[i].first);
        s[k]+=add[i].second;
    }

    for(i=1;i<=a.size();i++)  //存储坐标前缀和
    {
        s[i]+=s[i-1];
    }

    for(i=0;i<m;i++)   //处理区间差分询问
    {
        l=find(ask[i].first);
        r=find(ask[i].second);
        cout<<s[r]-s[l-1]<<endl;
    }

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla