HDU1166敌兵布阵
原题链接
HDU1166
题目抽象
给出一串数,要求
1)单点加减修改
2)区间查询
做法
树状数组,线段树,zkw。
尤其:如果常数不能像我的一样小,请用特技(scanf)。
代码
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
inline int lowbit(int x)
{
return x&-x;
}
const int maxn = 5e4 + 10;
int a[maxn];
int n;
void add(int x, int v)
{
while(x <= n)
{
a[x] += v;
x += lowbit(x);
}
}
int query(int x)
{
int ans = 0;
while(x > 0)
{
ans += a[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
int t;
cin>>t;
for(int i = 1; i <= t; i++)
{
cout<<"Case "<<i<<":"<<endl;
memset(a, 0, sizeof a);
cin>>n;
for(int j = 1; j <= n; j++)
{
int tmp;
cin>>tmp;
add(j, tmp);
}
string type;
while(cin>>type && type != "End")
{
if(type == "Add")
{
int x, v;
cin>>x>>v;
add(x, v);
}
else if(type == "Sub")
{
int x, v;
cin>>x>>v;
add(x, -v);
}
else if(type == "Query")
{
int x, y;
cin>>x>>y;
cout<<query(y)-query(x-1)<<endl;
}
}
}
return 0;
}