/*
三种操作
0 x y 把x位置的值改成y
1 x y 交换x与y位置的值
2 x y 统计[x,y]中连续k个值的最大值
我们把1-k的和值作为b[1],2-(k+1)的和值作为b[2],以此类推
那么可以建立一棵[1,n-k+1]的线段树
求连续k个和的最大值,退化为求某个区间的最值问题
线段树中有延迟操作,优化时间效率
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
using namespace std;
const int N=200009;
int n,m,k,num;
int v[N],b[N];
struct Node
{
int L,R,mid,v,lazy;//v保存线段中的最大值,lazy保存未释放的值
}node[N*5];
int create(int t,int L,int R)
{
node[t].L=L;
node[t].R=R;
node[t].mid=(L+R)>>1;
node[t].lazy=0;
if(L==R)
{
node[t].v=b[L];
return b[L];
}
node[t].v=max(create(t<<1,L,node[t].mid),create(t<<1|1,node[t].mid+1,R));
return node[t].v;
}
void init()
{
int i,j,t=0;
scanf("%d%d%d",&n,&m,&k);
num=n-k+1;
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
memset(b,0,sizeof(b));
for(int i=1;i<=k;i++)b[1]+=v[i];
for(int i=2;i<=n-k+1;i++)b[i]=b[i-1]-v[i-1]+v[i+k-1];
create(1,1,num);//以b数组建线段树
}
void down(int t)//把lazy值释放给子节点
{
if(node[t].L==node[t].R)return ;
node[t<<1].v+=node[t].lazy;
node[t<<1].lazy+=node[t].lazy;
node[t<<1|1].v+=node[t].lazy;
node[t<<1|1].lazy+=node[t].lazy;
node[t].lazy=0;
}
void up(int t)//子节点值改变后更新父节点的最大值
{
if(node[t].L==node[t].R)return ;
node[t].v=max(node[t<<1].v,node[t<<1|1].v);
}
int query(int t,int L,int R)
{
int mid=(L+R)>>1;
if(node[t].L==L&&node[t].R==R)
{
return node[t].v;
}
if(node[t].lazy)//有未释放的值先释放
{
down(t);
}
if(R<=node[t].mid)
{
return query(t<<1,L,R);
}
else if(L>node[t].mid)
{
return query(t<<1|1,L,R);
}
else
{
return max(query(t<<1,L,node[t].mid),query(t<<1|1,node[t].mid+1,R));
}
}
void set_val(int t,int L,int R,int v)
{
int mid=(L+R)>>1;
if(node[t].L==L&&node[t].R==R)
{
node[t].v+=v;
node[t].lazy+=v;
return ;
}
if(node[t].lazy)//有未释放的值先释放
{
down(t);
}
if(R<=node[t].mid)
{
set_val(t<<1,L,R,v);
}
else if(L>node[t].mid)
{
set_val(t<<1|1,L,R,v);
}
else
{
set_val(t<<1,L,node[t].mid,v);
set_val(t<<1|1,node[t].mid+1,R,v);
}
up(t);//子节点值改变可能会影响父节点,需要更新一遍
}
void solve()
{
int op,a,b;
while(m--)
{
scanf("%d%d%d",&op,&a,&b);
if(op==0)
{
set_val(1,max(1,a-k+1),min(a,num),b-v[a]);//把a位置的值设成b,表现为线段[max(1,a-k+1),min(a,num)]加上b-v[a];
v[a]=b;
}
else if(op==1)
{
if(a==b)continue;
set_val(1,max(1,a-k+1),min(a,num),v[b]-v[a]);
set_val(1,max(1,b-k+1),min(b,num),v[a]-v[b]);
swap(v[a],v[b]);
}
else
{
printf("%d\n",query(1,a,b-k+1));
}
}
}
int main(){
int T;
scanf("%d", &T);
while (T--)
{
init();
solve();
}
return 0;
}
分享到:
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
POJ题解 个人写法 线段树每个人都不一样
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1746750
极角的实际应用很广,然而编程解决这类问题不像数学里所描述的那么简单,因为计算机的实数无法像现实生活中的那么精确。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告