hdu-1166敌兵布阵

这个题目就是考察线段树的基本用法，我自己打了代码，其实就是照模板来的，大概思想已经弄懂了。用c++不能过，说我超时，就改成c的读入读出，这坑爹的过了。我最爱的c++，你肿么了。。。

这是ac的代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;int n,m;
int num[100005];struct H
{int l,r,sum;
}trees[300005];void build_trees(int jd,int l,int r)
{trees[jd].l=l;trees[jd].r=r;if(l==r){trees[jd].sum=num[l];return ;}int mid = (l+r)/2;build_trees(jd*2,l,mid);build_trees(jd*2+1,mid+1,r);trees[jd].sum=trees[jd*2].sum+trees[jd*2+1].sum;
}void update(int jd,int a,int b)
{if(trees[jd].l==trees[jd].r)trees[jd].sum+=b;else {int mid = (trees[jd].l+trees[jd].r)/2;if(a<=mid) update(jd*2,a,b);else update(jd*2+1,a,b);trees[jd].sum=trees[jd*2].sum+trees[jd*2+1].sum;}
}int query(int jd , int l,int r)
{if(l<=trees[jd].l&&r>=trees[jd].r)return trees[jd].sum;int ans=0;int mid = (trees[jd].l+trees[jd].r)/2;if(l<=mid) ans+=query(jd*2,l,r);if(r>mid)  ans+=query(jd*2+1,l,r);return ans;
}int main()
{int t;int i,j,cas;int a,b;char st[10];scanf("%d",&t);for(cas=1;cas<=t;cas++){memset(num,0,sizeof num);scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&num[i]);}build_trees(1,1,n);printf("Case %d:\n",cas);for(;;){scanf("%s",st);if(st[0]=='E')break;scanf("%d%d",&a,&b);if(st[0]=='A')update(1,a,b);if(st[0]=='S')update(1,a,-b);if(st[0]=='Q')printf("%d\n",query(1,a,b));}}return 0;
}

这是没ac的代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;int n,m;
int num[100005] = {0};struct H
{int l,r,sum;
}trees[300005];void build_trees(int jd,int l,int r)
{trees[jd].l=l;trees[jd].r=r;if(l==r){trees[jd].sum=num[l];return ;}int mid = (l+r)/2;build_trees(jd*2,l,mid);build_trees(jd*2+1,mid+1,r);trees[jd].sum=trees[jd*2].sum+trees[jd*2+1].sum;
}void update(int jd,int a,int b)
{if(trees[jd].l==trees[jd].r)trees[jd].sum+=b;else {int mid = (trees[jd].l+trees[jd].r)/2;if(a<=mid) update(jd*2,a,b);else update(jd*2+1,a,b);trees[jd].sum=trees[jd*2].sum+trees[jd*2+1].sum;}
}int query(int jd , int l,int r)
{if(l<=trees[jd].l&&r>=trees[jd].r)return trees[jd].sum;int ans=0;int mid = (trees[jd].l+trees[jd].r)/2;if(l<=mid) ans+=query(jd*2,l,r);if(r>mid)  ans+=query(jd*2+1,l,r);return ans;
}int main()
{int l,r;cin >> m;char s[10];for(int j = 1;j <= m;j++){cin >> n;for(int i = 1;i <= n;i++){cin >> num[i];}build_trees(1,1,n);cout << "Case " << j << endl;while(1){cin >> s;if(s[0] == 'E'){break;}else if(s[0] == 'Q'){cin >> l >> r;int ans = query(1,l,r);cout << ans << endl;}else if(s[0] == 'A'){cin >> l >> r;update(1,l,r);}else if(s[0] == 'S'){cin >> l>> r;update(1,l,-r);}}}return 0;
}