强行CDQ分治了一波。

麻辣鸡,=+ 和 if();找了20分钟

暴力/////////////////

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
class hhh{
public:
int rc,lc;
long long int sum;
}a[1000010]={0};
void init(int lc,int rc,int root)
{
a[root].rc=rc;
a[root].lc=lc;
if(rc==lc)
return;
int mid=(lc+rc)/2;
init(lc,mid,root*2);
init(mid+1,rc,root*2+1);
}
void add(int root,int d,int k)
{
a[root].sum+=d;
if(a[root].rc==a[root].lc)
return;
int mid=(a[root].rc+a[root].lc)/2;
if(k<=mid)
add(root*2,d,k);
if(k>=mid+1)
add(root*2+1,d,k);
}
long long summ(int root,int lc,int rc)
{
if(a[root].lc==lc&&a[root].rc==rc)
return a[root].sum;
int mid=(a[root].lc+a[root].rc)/2;
if(rc<=mid)
return summ(root*2,lc,rc);
if(lc>=mid+1)
return summ(root*2+1,lc,rc);
return summ(root*2,lc,mid)+summ(root*2+1,mid+1,rc);
}
int main()
{
string c;
freopen("shulie.in","r",stdin);
freopen("shulie.out","w",stdout);
int b,n,m;
cin>>n;
init(1,n,1);
for(int i=1;i<=n;i++)
{
cin>>b;
add(1,b,i);
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>c;
if(c=="ADD")
{
int x,y;
cin>>x>>y;
add(1,y,x);
}
if(c=="SUM")
{
int x,y;
cin>>x>>y;
cout<<summ(1,x,y)<<' ';
}
}
return 0;
}

回复 @Letter zZZz :
看不懂+1

...

表示你们的模拟怎么都跑的这么快

用这个练习splay真是智障

zkw线段树跑了0.4s 果然还是树状数组最快啊

回复 @Janis :
打开链接身份后海空军飞机库萨芬黄金时段灰灰姐 环境萨哈夫经典怀旧啊哈樊江路口减少客户健康 驹留空谷，吗年历卡看病贵几乎是看见高科技 艰苦的尽快建立，播放机开或关带加号的快更快交点罚款 科技的韩国进口付好款铄金毁骨房价格书法家改了规划建；精度高黄酒克黄酒克 开机后归属感款到发货国际快递华工科技发挥更加科 就会觉得还能帮忙宣传吗 会计师鼓风机可回收空间规划思考空间狗 海空军韩国进口工会经费大客户结果可能不信呢； 进口货国际卡很发达金属构件大虎沟街道法国红酒华电国际 付款交单规划阶段，别那么操心， 发动机号感觉韩国空军

学改段求点和改点求段学晕了，差点不会写。。。

线段树

评测姬已超神……

这题有一个数据比数列操作b和数列操作c还强！笨算法超时了。。。

回复 @(无定义) :
[size=50]怪我咯[/size]

回复 @叶子の宿敌 :
你这样大小号配合留名真的好吗-_-？

[size=50]刘明[/size]

[size=35]Go X[/size]

没注意下标WA一次。。