线段树的单点更新+区间求和
hdu1166敌兵布阵
Input
第一行一个整数T,表示有T组数据。
每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地
,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
接下来每行有一条命令,命令有4种形式:
(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
(4)End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令
Output
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
Sample Output
Case 1:
6
33
59
结构体实现的代码
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=50005;
int num[maxn];
char str[30];
int n;
typedef struct node{
int left,right,data;
node* lchild;
node* rchild;
node(){
left=right=data=0;
}
}tree;
int sum;
tree* create(int a,int b){
tree *r;
r=(tree*)malloc(sizeof(tree));
r->left=a;
r->right=b;
if(a==b){
r->data=num[a];
r->lchild=r->rchild=NULL;
}
else{
int mid=(a+b)>>1;
r->lchild=create(a,mid);
r->rchild=create(mid+1,b);
r->data=r->lchild->data+r->rchild->data;
}
return r;
}
void updata(tree *r,int a,int b){
if(r->left==a&&r->right==a){
r->data+=b;
return;
}
int mid=(r->left+r->right)>>1;
if(a<=mid)
updata(r->lchild,a,b);
else{
updata(r->rchild,a,b);
}
r->data+=b;
}
void find(tree *r,int a,int b){
if(r->left==a&&r->right==b){
sum+=r->data;
return;
}
int mid=(r->left+r->right)>>1;
if(b<=mid)
find(r->lchild,a,b);
else if(a>mid)
find(r->rchild,a,b);
else{
find(r->lchild,a,mid);
find(r->rchild,mid+1,b);
}
}
int main(){
int t;
int cas=1;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&num[i]);
}
tree *T;
T=create(1,n);
int a,b;
printf("Case %d:
",cas++);
while(scanf("%s",str)!=EOF){
if(str[0]=='E')
break;
scanf("%d%d",&a,&b);
if(str[0]=='A')
updata(T,a,b);
else if(str[0]=='S')
updata(T,a,-b);
else{
sum=0;
find(T,a,b);
printf("%d
",sum);
}
}
}
return 0;
}
hdu1754单点更新+区间求最大值
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ,和两个正整数A,B。
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作,在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
代码
数组实现
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int Maxn=200005;
struct node{
int Max,left,right;
}tree[Maxn*3];
int val[Maxn];
int create(int root,int left,int right){
tree[root].left=left;
tree[root].right=right;
if(left==right)
return tree[root].Max=val[left];
int a,b,mid=(left+right)>>1;
a=create(root<<1,left,mid);
b=create(root<<1|1,mid+1,right);
return tree[root].Max=max(a,b);
}
int updata(int root,int pos,int val){
if(pos<tree[root].left||tree[root].right<pos)
return tree[root].Max;
if(tree[root].left==pos&&tree[root].right==pos)
return tree[root].Max=val;
int a,b;
a=updata(root<<1,pos,val);
b=updata(root<<1|1,pos,val);
return tree[root].Max=max(a,b);
}
int cal(int root,int left,int right){
if(tree[root].left>right||tree[root].right<left)
return 0;
if(tree[root].left>=left&&tree[root].right<=right)
return tree[root].Max;
int a,b;
a=cal(root<<1,left,right);
b=cal(root<<1|1,left,right);
return max(a,b);
}
int main(){
int n,q;
while(scanf("%d%d",&n,&q)!=EOF){
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
int tmp_1=create(1,1,n);
char c;
getchar();
for(int i=1;i<=q;i++){
int a,b;
scanf("%c %d %d",&c,&a,&b);
getchar();
if(c=='Q'){
int ans=cal(1,a,b);
printf("%d
",ans);
}
else{
int tmp_2= updata(1,a,b);
}
}
}
return 0;
}
hdu1698区间更新+区间求和
在一款游戏dota中,有一个人物叫帕吉,他有一个钩子,钩子的每一节可能是不同的材质,有的是铜的,有的是银的
,有的是金的,每一节铜钩子的价值是1,银钩子的价值是2,金钩子的价值是3。帕吉现在想对钩子做一些操作,然后
求出钩子的总价值。
数据的第一行是测试数据组数。
对于每组测试数据,第一行是一个数字N,代表帕吉钩子的节数,
也就是长度;第二行是一个数字Q,代表帕吉要对钩子进行几次操作,接下来Q行,每行有三个数字X、Y和Z,代表把钩
子的第X节到第Y节修改成第Z种材质(第一种:铜;第二种:银;第三种:金)。
对于每组测试数据,输出帕吉钩子的价值。
1
10
2
1 5 2
5 9 3
代码
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define MAXSIZE 1000000
int val[MAXSIZE];
int add[100010<<2];
int sum[100010<<2];
struct node
{
int total;
int left;
int right;
int mark; //延时标记
} tree[MAXSIZE*3];
//下面两种create都可以,选择一种就可
//int create(int root,int left,int right)
//{
// add[root]=0;
// sum[root]=1;
// tree[root].left=left;
// tree[root].right=right;
// if(left==right)
// return tree[root].total=val[left];
// int middle=(left+right)>>1;
// return tree[root].total=create(root<<1,left,middle)+create(root<<1|1,middle+1,right);
//}
void create(int root,int left,int right)
{
add[root]=0;
sum[root]=1;//初始值为1,如果为0,有些在更新中没有更新到的节点值就为0了;
tree[root].left=left;
tree[root].right=right;
if(left==right)
return ;
int middle=(left+right)>>1;
create(root<<1,left,middle);
create(root<<1|1,middle+1,right);
}
// 参数:询问区间左端点,询问区间右端点,每个位置需要增加的值,当前节点序号
void update(int L, int R, int x, int root)
{
if (L<=tree[root].left && tree[root].right<= R)
{
// 当前区间被包含,处理相应附加信息
add[root] = x; // 更新延迟标记
sum[root] = x * (tree[root].right-tree[root].left+1);
return; // 暂时不用再向下递归
}
int mid = (tree[root].left+tree[root].right)>>1;
if (add[root]) // 延迟标记不为0,说明有未完成的更新,更新之
{
add[root<<1] = add[root];
add[root<<1|1] = add[root];
sum[root<<1] = add[root] * (mid-tree[root].left+1);
sum[root<<1|1] = add[root] * (tree[root].right-mid);
add[root] = 0; // 不要忘了去除延迟标记
}
if (L <= mid) // 左子区间中包含有更新区间的部分,需要更新
update(L, R, x, root<<1);
if (R > mid) // 右子区间中包含有更新区间的部分,需要更新
update(L, R, x, root<<1|1);
sum[root] = sum[root<<1] + sum[root<<1|1];//从叶子节点向上更新
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1,n,q; i<=t; i++)
{
memset(sum,0,sizeof(sum));
memset(add,0,sizeof(add));
scanf("%d%d",&n,&q);
for(int j=1; j<=n; j++)
val[j]=1;
create(1,1,n);
for(int j=0,x,y,z; j<q; j++)
{
scanf("%d%d%d",&x,&y,&z);
update(x,y,z,1);
}
printf("Case %d: The total value of the hook is %d.
",i,sum[1]);
}
}
线段树的区间合并&&求区间的最长公共子序列
假设有一列数{Ai}(1≤i≤n),支持如下两种操作:
U A B: 将第A个数变成值 B
Q A B: 输出区间[A,B]的最长连续递增子序列的长度
区间的最大连续递增子序列(下面统称LCIS)的长度
las[i]??? i 号节点对应区间包含左端点最长的LCIS长度
ras[i]??? i 号节点对应区间包含右端点最长的LCIS长度
mov[i] 表示i节点(线段)对应的LCIS的长度
///i表示的是节点,即线段树节点
例如当前节点i 对应的区间的序列为:
1 2 5 2 1 0 4 2 6
则 las[i] = 3, ras[i] = 2, 同时,mov[i] = 3
对于线段树中某个节点 i ,它的 mov[i] 值应该是以下几种情况的最大值:
(1)左儿子 ls 节点的 mov[ls] 值
(2) 右儿子 rs 节点的 mov[rs] 值
(3) 左右儿子区间合并之后得到的LCIS值。
从刚刚的例子中我们发现: 区间合并得到的LCIS
一定跨越左右儿子两个区间,
因此其必然经过当前节点对应区间中间的两个数!
我们可以用上面的后两个数组来表示出来,即:
///ras[ls] + las[rs]
用语言表达就是:
///从左儿子对应区间的右端点向左延伸的最大LCIS长度 加上
///从右儿子对应区间的左端点向右延伸的最大LCIS长度
首先是建树:
///建树模版
int build(int root,int l,int r)
{
if(l==r)
{
scanf("%d",&a[l]);
ras[root]=las[root]=1;
mov[root]=1;
return;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(l,mid,r,root);
}
void pushup(int l,int mid,int r,int root)
{
las[root]=las[root<<1];
ras[root]=ras[root<<1|1];
mov[root]=0;
if(a[mid]<a[mid+1])
{
mov[root]=ras[root<<1]+las[root<<1|1]
if(las[root<<1]==mid-l+1)
las[root]+=las[root<<1|1];
if(ras[root<<1|1]==r-mid)
ras[root]+=ras[root<<1];
}
mov[root]=max(mov[root],max(mov[root<<1],mov[root<<1|1]));
}
///查询操作
int query(int L, int R,///L,R为要查询的区间, int l, int r, int rt){
if (L<=l && r<=R)
return mov[rt];
int mid=(l+r)>>1;
int res=0;
if (R <= mid)
return query(L, R, l, mid, rt<<1);
else if (L > mid)
return query(L, R, mid+1, r, rt<<1|1);
else {
int t1 = 0, t2 = 0, t3 = 0;
t1 = query(L, R, l, mid, rt<<1);
t2 = query(L, R, mid+1, r, rt<<1|1);
if (va[mid] < va[mid+1]) // 注意约束条件
t3 = min(ras[rt<<1],mid-L+1) + min(las[rt<<1|1],R-mid);
return max(t3,max(t1,t2));
}
return res;
}
还有一个操作:
(1) U A B: 将第A个树变成值 B
这个是之前单点更新操作的实现类似
,唯一需要注意的地方就是维护节点信息的时候用到了和建树相同的pushup() 操作
线段树的扫描线问题
输入就是若干个矩形的坐标,求这些矩形的面积并
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=200+10;
int mark[MAX<<2];//记录某个区间的下底边比上底边多的个数
double sum[MAX<<2];//记录某个区间下底边比上底边多的个数总长度
double Hash[MAX];//对横坐标x离散化
struct seg //线段
{
double l,r,h;
int d;
seg() {}
seg(double x1,double x2,double H,int D):l(x1),r(x2),h(H),d(D) {}//构造函数
bool operator<(const seg &a)const//自定义结构体排序
{
return h<a.h;
}
} s[MAX];
void Upfather(int n,int left,int right){
if(mark[n])
sum[n]=Hash[right+1]-Hash[left];//表示该区间整个线段长度可作为底边
else if(left == right)
sum[n]=0;//叶子结点区间长度为0,则底边长度为0
else
sum[n]=sum[n<<1]+sum[n<<1|1];
}
void Update(int L,int R,int d,int n,int left,int right){
if(L<=left && right<=R) //该区间是当前扫描线段的一部分
{
mark[n]+=d;//更新上下底边之差
Upfather(n,left,right);//更新可用底边长
return;
}
int mid=left+right>>1;
if(L<=mid)
Update(L,R,d,n<<1,left,mid);
if(R>mid)
Update(L,R,d,n<<1|1,mid+1,right);
Upfather(n,left,right);
}
int search(double key,double *x,int n){//Search函数是为了找到x坐标为key时,hash数组的下标
int left=0,right=n-1;
while(left<=right){
int mid=(left+right)>>1;
if(x[mid] == key)
return mid;
else if(x[mid]>key)
right=mid-1;
else
left=mid+1;
}
return -1;
}
int main(){
double x1=0,y1=0,x2=0,y2=0;
while(x1 != -2){
int size=0;
while(cin>>x1>>y1>>x2>>y2,x1>=0){
if(x1>x2)swap(x1,x2);
if(y1>y2)swap(y1,y2);
Hash[size]=x1;
s[size++]=seg(x1,x2,y1,1);
Hash[size]=x2;
s[size++]=seg(x1,x2,y2,-1);
}
sort(Hash,Hash+size);//把x坐标从小到大排序
sort(s,s+size);//把线段按高度h从小到大排序
int k=1;
for(int i=1; i<size; ++i) //去重复端点
{
if(Hash[i] != Hash[i-1])
Hash[k++]=Hash[i];
}
double ans=0;
for(int i=0; i<size; ++i){
int L=search(s[i].l,Hash,k);
int R=search(s[i].r,Hash,k)-1;
Update(L,R,s[i].d,1,0,k-1);//扫描线段更新可用底边长
ans+=sum[1]*(s[i+1].h-s[i].h);//新增加面积
}
cout<<ans<<endl;
}
return 0;
}