luogu T96516 [DBOI2019]持盾 可持久化线段树+查分
2024-08-22 13:42:02
因为题中的操作是区间加法,所以满足前缀相减性.
而每一次查询的时候还是单点查询,所以直接用可持久化线段树维护差分数组,然后查一个前缀和就行了.
code:
#include <bits/stdc++.h>
#define N 200004
#define LL long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,m,q,tot,rt[N];
LL val[N];
int newnode() { return ++tot; }
struct node { int ls,rs; LL sum;}t[N*50];
void build(int &now,int l,int r)
{
now=newnode();
if(l==r) return ;
int mid=(l+r)>>1;
if(l<=mid) build(t[now].ls,l,mid);
if(r>mid) build(t[now].rs,mid+1,r); }
int update(int p,int l,int r,int pos,int v)
{
int now=newnode();
t[now]=t[p];
t[now].sum=t[p].sum+1ll*v;
if(l==r) return now;
int mid=(l+r)>>1;
if(pos<=mid) t[now].ls=update(t[p].ls,l,mid,pos,v);
else t[now].rs=update(t[p].rs,mid+1,r,pos,v);
return now;
}
LL query(int now,int l,int r,int L,int R)
{
if(!now) return 0;
if(l>=L&&r<=R) return t[now].sum;
int mid=(l+r)>>1;
LL re=0ll;
if(L<=mid) re+=query(t[now].ls,l,mid,L,R);
if(R>mid) re+=query(t[now].rs,mid+1,r,L,R);
return re;
}
int main()
{
// setIO("input");
int i,j;
scanf("%d%d%d",&n,&m,&q);
for(i=1;i<=n;++i) scanf("%lld",&val[i]);
build(rt[0],1,n);
for(i=1;i<=m;++i)
{
int l,r,h;
scanf("%d%d%d",&l,&r,&h);
rt[i]=update(rt[i-1],1,n,l,h);
if(r<n) rt[i]=update(rt[i],1,n,r+1,-h);
}
for(i=1;i<=q;++i)
{
int opt;
scanf("%d",&opt);
if(opt==1)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
LL L=query(rt[x-1],1,n,1,z);
LL R=query(rt[y],1,n,1,z);
printf("%lld\n",R-L+val[z]);
}
else
{
int pos,p;
scanf("%d%d",&pos,&p);
val[pos]=1ll*p;
}
}
return 0;
}
最新文章
- JQUERY 测验
- Nginx+tomcat负载均衡时静态页面报404
- 004_URL 路由 - URL 路由
- ArcGIS制图之Sub Points点抽稀
- JS键盘事件监听
- Tomcat启动时自动加载一个类
- Android SoundPool.play方法的音量与系统音量的关系
- A-Frame_简单介绍
- 10个实用的PHP正则表达式
- mysql limit性能问题
- Android应用程序窗口(Activity)的窗口对象(Window) 的创建过程分析
- [linux]chown和chmod命令
- Java自然语言处理NLP工具包
- vue1.0和vue2.0的区别(二)
- 使用插件bootstrap-table实现表格记录的查询、分页、排序等处理
- div的默认position值是静态的static
- springboot启动的时候日志缺少Mapping日志等
- Android Studio 添加已经移除的Module
- [Spark][Python]获得 key,value形式的 RDD
- Python3 笔记