额然后你就发现可以 cdq()
by bamboo1030 @ 2023-08-23 18:22:54
No,我发现了可以用```vector```,```set```不好用。
```cpp
#include<cstdio>
#include<vector>
using namespace std;
int main(int argc,char **argv){
int maxn,maxm,temp,oper,addton,asked;
vector<int> data(1,0),first,last,add;
pair<int,int> range;
scanf("%d %d",&maxn,&maxm);
for(int iter=1;iter<=maxn;iter++){
scanf("%d",&temp);
data.push_back(temp);
};
while(maxm--){
scanf("%d",&oper);
if(oper==1){
scanf("%d %d %d",&range.first,&range.second,&addton);
first.push_back(range.first);
last.push_back(range.second);
add.push_back(addton);
}else{
scanf("%d",&asked);
int sum=data[asked];
for(int iter=0;iter<add.size();iter++){
if(first[iter]<=asked&&asked<=last[iter]){
sum+=add[iter];
};
};
printf("%d\n",sum);
};
};
return 0;
};
```
by Kapo_Hisy @ 2023-08-23 18:35:15
然后发现没法挣扎,70分TLE,优化不了
by Kapo_Hisy @ 2023-08-23 18:36:03
和正常暴力一样,还是那个点错。
by Kapo_Hisy @ 2023-08-23 18:39:02
但是也优化了一些,有些测试点八十多毫秒,全优化成二十六毫秒。
by Kapo_Hisy @ 2023-08-23 18:40:51
@[Myself_Hisy](/user/922691) 你说有没有一种可能,你这个程序复杂度 $O(n^2)$,根本过不了
by SJH_qwq @ 2023-08-23 18:43:49
线段树不熟练,懒得写,树状数组不会,~~这是对骗分技术的否认!~~
by Kapo_Hisy @ 2023-08-23 18:45:48
可以用FHQ-treap
by Libingyue2011 @ 2023-08-23 19:15:17
可以分块暴力,只不过要快读才能过
by asas111 @ 2023-09-27 21:42:26