顶呱呱做网站,西安网站建设公司排名,海口网约车从业资格证,网站群建设存在的问题var说明add存储了插入操作#xff0c;在指定 x x x下标所在位置 a [ x ] c a[x]c a[x]cquery是求 [ L , R ] [L,R] [L,R]区间和用到的数组,最后才用到alls 是存储离散化之后的值 , 对于会访问到的每个下标#xff0c;统统丢到 a l l s 里面 #xff0c;会把 x 和 [ L , R …
var说明add存储了插入操作在指定 x x x下标所在位置 a [ x ] c a[x]c a[x]cquery是求 [ L , R ] [L,R] [L,R]区间和用到的数组,最后才用到alls 是存储离散化之后的值 , 对于会访问到的每个下标统统丢到 a l l s 里面 会把 x 和 [ L , R ] 都丢到 a l l s 里面不同的 [ L , R ] 有可能会重复输入 比如询问 [ 4 , 6 ] , [ 4 , 9 ] 的区间和 , 因此有必要去重调用 a l l s . e r a s e 是存储离散化之后的值,对于会访问到的每个下标统统丢到alls里面 \\ 会把x和[L,R]都丢到alls里面不同的[L,R]有可能会重复输入\\ 比如询问[4,6],[4,9]的区间和,因此有必要去重调用alls.erase 是存储离散化之后的值,对于会访问到的每个下标统统丢到alls里面会把x和[L,R]都丢到alls里面不同的[L,R]有可能会重复输入比如询问[4,6],[4,9]的区间和,因此有必要去重调用alls.erasefind 在 a l l s 里面二分查找 返回 r 1 是想要做前缀和下标要从 1 开始算直接 r e t u r n r 会把下标从 0 开始算 r e t u r n r 1 就是 r ≥ 0 , f i n d 返回值是 ≥ 1 , 返回值从 1 开始算 在alls里面二分查找\\返回r1是想要做前缀和下标要从1开始算直接return \,\,\,\, r会把下标从0开始算\\return \,\,\,r1就是r\ge0,find返回值是\ge1,返回值从1开始算 在alls里面二分查找返回r1是想要做前缀和下标要从1开始算直接returnr会把下标从0开始算returnr1就是r≥0,find返回值是≥1,返回值从1开始算
思路 把不同的 ∀ i ∈ [ 0 , m − 1 ] 把 [ L , R ] i \forall i\in [0,m-1]把[L,R]_i ∀i∈[0,m−1]把[L,R]i区间输入到 q u e r y query query
把不同的 ∀ i ∈ [ 0 , n − 1 ] 把 { x , c } i \forall i\in [0,n-1]把\{x,c\}_i ∀i∈[0,n−1]把{x,c}i输入到 a d d add add
把不同的 ∀ i ∈ [ − inf , inf ] 把会访问到的坐标轴的下标位置 i d x i \forall i\in [-\inf,\inf]把会访问到的坐标轴的下标位置idx_i ∀i∈[−inf,inf]把会访问到的坐标轴的下标位置idxi输入到 a l l s alls alls, i d x i 来自于 [ L , R ] i 的 L 和 R 还有 { x , c } i 里面的 x idx_i来自于[L,R]_i的L和R还有\{x,c\}_i里面的x idxi来自于[L,R]i的L和R还有{x,c}i里面的x就这三个来源
1.应用离散化的方法初始化queryadd和alls 2. a 在 x 位置加上 c 先把 x 位置通过 f i n d 函数得到离散化之后的坐标 i d x 然后 a [ i d x ] c , 完成 c a在x位置加上c先把x位置通过find函数得到离散化之后的坐标idx然后a[idx]c,完成c a在x位置加上c先把x位置通过find函数得到离散化之后的坐标idx然后a[idx]c,完成c 3. 对 a 求前缀和存到 b 里面 对a求前缀和存到b里面 对a求前缀和存到b里面 4. 遍历 q u e r y 对于每个 p a i r i n t , i n t 类型的 [ L , R ] i , 我们也是要先分别通过 f i n d 函数分别获取 L R 在离散化之后的下标 然后根据离散化之后建立的前缀和数组 b 来直接求区间和 遍历query\\对于每个pairint,int 类型的[L,R]_i,我们也是要先分别通过find函数分别获取LR在离散化之后的下标\\然后根据离散化之后建立的前缀和数组b来直接求区间和 遍历query对于每个pairint,int类型的[L,R]i,我们也是要先分别通过find函数分别获取LR在离散化之后的下标然后根据离散化之后建立的前缀和数组b来直接求区间和 总结 题目要求区间和然后可以用前缀和解决问题但是这个问题是如果直接开辟一个巨大的数组然后在许多是0的位置反复计算0会很费劲然后可以用离散化的方法减少计算量只在需要访问的下标位置c减少计算量降低时间复杂度。 时间复杂度分析 vector.erase的复杂度是 O ( k ) k 是重复的元素 O(k)k是重复的元素 O(k)k是重复的元素 二分查找是 O ( l o g n ) O(logn) O(logn) 排序是 O ( n l o g n ) O(nlogn) O(nlogn) 然后求前缀和是 O ( n ) O(n) O(n) 总得来说是 O ( n l o g n ) O ( k ) O ( n l o g n ) O(nlogn) O(k)O(nlogn) O(nlogn)O(k)O(nlogn)
#includealgorithm
#includeiostream
#define N 300086
using namespace std;
int n,m,x,a[N],b[N];
typedef pairint,int PII;
vectorPII add,query;
vectorint alls;
//在alls里面二分查找
//返回r1是想要做前缀和下标要从1开始算直接return r会把下标从0开始算
//return r1就是r≥0,find返回值是≥1,返回值从1开始算
int find(int x){int l0,ralls.size()-1;while(lr){int midlr1;if(alls[mid]x) rmid;else lmid1;}return r1;
}
int main(){cinnm;for(int i0;in;i){int x,c;cinxc;add.push_back({x,c});alls.push_back(x);}for(int i0;im;i){int l,r,c;cinlr;query.push_back({l,r});alls.push_back(l);alls.push_back(r);}sort(alls.begin(),alls.end());alls.erase(unique(alls.begin(),alls.end()),alls.end());for(auto item:add){int idxfind(item.first);a[idx]item.second;}for(int i1;ialls.size();i){b[i]b[i-1]a[i];}for(const auto item:query){int lfind(item.first),rfind(item.second);coutb[r]-b[l-1]endl;}return 0;
}
