HDOJ1166 敌兵布阵
2024-08-30 00:34:36
赤裸裸的线段树，借个模板，改写一下即可。
代码：
#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<cstring>
using namespace std;
struct line{
int left,right,n;
int mid(){return (left+right)/2;}
}a[50010<<2];
unsigned short num[50010];
void build(int l,int r,int step)
{
a[step].left=l;
a[step].right=r;
if(l==r)
{
a[step].n=num[l];
return;
}
int mid=a[step].mid();
build(l,mid,step*2);
build(mid+1,r,step*2+1);
a[step].n=a[step*2].n+a[step*2+1].n;
}
int query(int l,int r,int step)
{
if(a[step].left==l&&a[step].right==r)
return a[step].n;
int mid=a[step].mid();
if(mid>=r)
return query(l,r,step*2);
else if(mid<l)
return query(l,r,step*2+1);
else
return query(l,mid,step*2)+query(mid+1,r,step*2+1);
}
void Add(int l,int r,int step,int x,int y)
{
if(a[step].left==a[step].right&&a[step].right==x)
{
a[step].n+=y;
return ;
}
int mid=a[step].mid();
if(x>mid)
Add(mid,r,step*2+1,x,y);
else
Add(l,mid,step*2,x,y);
a[step].n=a[step*2].n+a[step*2+1].n;
}
void Sub(int l,int r,int step,int x,int y)
{
if(a[step].left==a[step].right&&a[step].right==x)
{
a[step].n-=y;
return ;
}
int mid=a[step].mid();
if(x>mid)
Sub(mid,r,step*2+1,x,y);
else
Sub(l,mid,step*2,x,y);
a[step].n=a[step*2].n+a[step*2+1].n;
}
int main()
{
int t,n;
scanf("%d",&t);
for(int tcase=1;tcase<=t;tcase++)
{
printf("Case %d:\n",tcase);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
build(1,n,1);
char in[6];
int x,y;
while(scanf("%s",&in)&&strcmp(in,"End")!=0)//字符数组匹配，弄得我好惨
{
scanf("%d%d",&x,&y);
if(strcmp(in,"Query")==0)
printf("%d\n",query(x,y,1));
else if(strcmp(in,"Sub")==0)
Sub(1,n,1,x,y);
else if(strcmp(in,"Add")==0)
Add(1,n,1,x,y);
}
}
return 0;
}
最新文章
- Linux学习之八--关闭firewall防火墙安装iptables并配置
- vbs连接sql server及写文件操作
- Git-Notes
- 探索软件工程道路上的我II (Θ∀Θ＃)
- Java类与对象——几个课堂例子的总结及作业
- linux内核分析——扒开系统调用的三层皮
- 使用XtraGrid自定义列计算1 z
- bzoj 1012 维护一个单调数列
- 剑指Offer45 约瑟夫环
- Jquery 模板插件 jquery.tmpl.js 的使用方法(2):嵌套each循环,temp调用(使用预编译的模板缓存)
- ActiveMQ(5.10.0) - Connection Configuration URI
- Git教程之分支管理之一
- HTML5 canvas translate() 方法
- web之Respone
- Chinese Rings hdu 2842 矩阵快速幂
- poj 2570 Fiber Network(floyd)
- pointer-events属性屏蔽鼠标事件（点击穿透上层元素）
- [leetcode]18. 4Sum四数之和
- AutoCompleteTextView 简单用法 实现自定义list adapter
- 用.Net打造一个移动客户端（Android/IOS）的服务端框架NHM（四）——Android端Http访问类(转)