hdu-1166

72 阅读 0 评论 48 点赞

我是靠谱客的博主故意天空，最近开发中收集的这篇文章主要介绍hdu-1166，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://acm.hdu.edu.cn/showproblem.php?pid=1166

线段树点操作

代码风格更新后：

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <vector>
#define Mid(a,b) ( a+((b-a)>>1))
#define ll(x) (x<<1)
#define rr(x) (x<<1|1)
const int N = 50010;
using namespace std;
int t,n;
int a[N];
struct node
{
int left;
int right;
int sum;
int mid() { return Mid(left, right); }
};
struct segtree
{
node tree[N * 4];
void buildtree(int left,int right,int ind)
{
tree[ind].left = left;
tree[ind].right = right;
tree[ind].sum = 0;
if (left == right)
tree[ind].sum = a[left];
else
{
int mid = tree[ind].mid();
buildtree(left,mid,ll(ind));
buildtree(mid+1,right,rr(ind));
tree[ind].sum = tree[ll(ind)].sum + tree[rr(ind)].sum;
}
}
void update(int pos,int ind,int val)
{
if (tree[ind].left == tree[ind].right) tree[ind].sum += val;
else
{
int mid = tree[ind].mid();
if (pos <= mid)
update(pos,ll(ind),val);
else
update(pos,rr(ind),val);
tree[ind].sum = tree[ll(ind)].sum + tree[rr(ind)].sum;
}
}
int query(int st ,int ed,int ind)
{
int left = tree[ind].left;
int right = tree[ind].right;
if (st <= left && right <= ed)
return tree[ind].sum;
else
{
int mid = tree[ind].mid();
int sum1 = 0;
int sum2 = 0;
if (st <= mid)
sum1 = query(st,ed,ll(ind));
if (ed > mid)
sum2 = query(st,ed,rr(ind));
return sum1 + sum2;
}
}
}seg;
int main()
{
scanf("%d",&t);
int cases = 1;
while (t--)
{
scanf("%d",&n);
for (int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
}
seg.buildtree(1, n, 1);
cout << "Case " << cases++ << ":" << endl;
char opr[20];
while (1)
{
scanf("%s",opr);
int c, d;
if (!strcmp(opr, "End"))
break;
scanf("%d %d",&c,&d);
if (!strcmp(opr, "Add"))
{
seg.update(c, 1, d);
}
else if (!strcmp(opr, "Sub"))
{
seg.update(c, 1, -d);
}
else if (!strcmp(opr, "Query"))
{
printf("%dn", seg.query(c, d, 1));
}
}
}
return 0;
}

之前

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include <sstream>
#include <time.h>
#include <utility>
#include <malloc.h>
using namespace std;
struct node
{
int left ;
int right;
int sum;
}b[5001000];
int a[5000010];
void build(int left ,int right ,int i)
{
int mid;
b[i].left =left;
b[i].right =right ;
if (left == right )
{
b[i].sum=a[left];
return ;
}
mid = (left + right )/2;
build(left ,mid,2*i);
build( mid+1,right ,2*i+1);
b[i].sum=b[i*2].sum+b[i*2+1].sum;
}
void add (int id,int num,int i)//add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）</span>
{
if(b[i].left == b[i].right )
{
b[i].sum += num;
return ;
}
else
{
b[i].sum=b[i].sum+num;
if (id<= b[i*2].right )
add (id,num,i*2);
else
add
(id,num,i*2+1);
}
}
int query (int left,int right ,int i)//query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;</span>
{
int mid;
if (b[i].right
== right && b[i].left ==left )
return b[i].sum ;
mid=(b[i].left +b[i].right )/2;
if (right <= mid)
return query (left ,right,2*i);
else if (left > mid)
return query (left ,right,2*i+1);
else
return query (left ,mid,2*i)+query (mid+1 ,right,2*i+1);
}
int main()
{
int t;
int l=1;
scanf ("%d",&t);
while (t--)
{
int n;
scanf ("%d",&n);
for (int i=1;i<=n;i++)
scanf ("%d",&a[i]);
build(1,n,1);
char bb[100];
int c,d;
printf("Case %d:n",l++);
while (scanf ("%s",bb)
&& strcmp (bb,"End"))
{
scanf ("%d%d",&c,&d);
if(!strcmp(bb,"Add"))
{
add(c,d,1);
}
else if(!strcmp(bb,"Sub"))
{
add(c,-d,1);
}
else if(!strcmp(bb,"Query"))
{
printf("%dn",query (c,d,1));
}
}
}
return 0;
}