说明 - 2022-05-05
本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。
洛谷 P3372 线段树模板1
#include <bits/stdc++.h>
const int N = 1e5+4;
typedef long long LL;
LL val[N<<2],lazy[N<<2];
int qu[N];
int n,m,x,y,k,op;
int getMid(int l,int r)
{
return (l+r) >> 1;
}
void build(int l,int r,int rt)
{
if(l == r) val[rt] = qu[r];
else{
int mid = getMid(l,r);
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
val[rt] = val[rt<<1] + val[rt<<1|1];
}
}
void pushdown(int l,int r,int rt)
{
if(!lazy[rt]) return;
int mid = getMid(l,r);
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
val[rt<<1] += lazy[rt]*(mid-l+1);
val[rt<<1|1] += lazy[rt]*(r-mid);
lazy[rt] = 0;
}
LL query(int sl,int sr,int l,int r,int rt)
{
if(sl >= l && sr <= r) return val[rt];
pushdown(sl,sr,rt);
int mid = getMid(sl,sr);
if(r <=mid) return query(sl,mid,l,r,rt<<1);
else if(l > mid) return query(mid+1,sr,l,r,rt<<1|1);
else return query(sl,mid,l,r,rt<<1) + query(mid+1,sr,l,r,rt<<1|1);
}
void update(int sl,int sr,int l,int r,int v,int rt)
{
if(sl >= l && sr <= r){
val[rt] += v*(sr-sl+1);
lazy[rt] += v;
return ;
}
pushdown(sl,sr,rt);
int mid = getMid(sl,sr);
if(r <= mid) update(sl,mid,l,r,v,rt<<1);
else if(l > mid) update(mid+1,sr,l,r,v,rt<<1|1);
else{
update(sl,mid,l,r,v,rt<<1);
update(mid+1,sr,l,r,v,rt<<1|1);
}
val[rt] = val[rt<<1] + val[rt<<1|1];
}
void show(int l,int r,int rt)
{
if(l == r) {printf("%lld ",val[rt]); return ;}
pushdown(l,r,rt);
int mid = getMid(l,r);
show(l,mid,rt<<1);
show(mid+1,r,rt<<1|1);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++){
scanf("%d",&qu[i]);
}
build(0,n-1,1);
for(int i=0; i<m; i++){
scanf("%d",&op);
if(op == 2){
scanf("%d%d",&x,&y);
printf("%lld\n",query(0,n-1,x-1,y-1,1));
}
else{
scanf("%d%d%d",&x,&y,&k);
update(0,n-1,x-1,y-1,k,1);
}
//show(0,n-1,1);
//std::cout << std::endl;
}
return 0;
}
CF1288E
https://www.luogu.com.cn/problem/CF1288E
最小的排名 可想而知，若发过消息，则是1，否则为初始值。
最大的排名 ，用线段树记录：
假设人数为N，发消息次数为M，则开一个区间大小为M+N的线段树，用于记录所有人的最大排名。前M位初始化为1，后N为为[1，2，3，4…N]。（代码中用qu[]数组模拟出这样的值，然后初始化线段树），初始化整形变量idx=M
把每个人的最小排名和最晚排名都初始化为其序号。
用qu[]数组记录每个人最后出现的位置。(发一次消息算出现一次，qu[]具体表示什么，看完下方的3条就明白了)
每当一个人i发消息：
1.更新这个人的最小排名为1，最大排名为max(原最大排名,线段树查询qu[i]位置的结果)
2.把区间[idx+1,qu[i]]即这个人以及之前所有人对应的区间+1（是否包含这个人时无所谓的）
3.然后把这个人提前为第一个人，即qu[i]改为出现的位置改为idx–（也可以先提前，这样的话线段树区间应该初始化为0），
输出答案时
最小排名即记录中的最小排名，直接输出
最大排名为max(记录中的最大排名，线段树查询qu[i]位置的结果)
#include
#include
#include
#include
#include
#include
#include
void pushdown(int rt)
{
if(!lazy[rt]) return;
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
lazy[rt] = 0;
}
void update(int sl,int sr,int l,int r,int val,int rt)
{
if(sl >=l && sr<=r) {
lazy[rt] += val;
return ;
}
pushdown(rt);
int mid = (sl+sr) >> 1;
if(l<=mid) update(sl,mid,l,r,val,rt<<1);
if(r>mid) update(mid+1,sr,l,r,val,rt<<1|1);
}
int query(int sl,int sr,int l,int r,int rt)
{
if(sl>=l && sr<=r){
return lazy[rt];
}
pushdown(rt);
int mid = (sl+sr) >> 1;
if(l<=mid) return query(sl,mid,l,r,rt<<1);
else return query(mid+1,sr,l,r,rt<<1|1);
}
int main()
{
scanf("%d%d",&n,&m);
idx = m;
for(int i=1; i<=n; i++){
span[i].second = span[i].first = i;
qu[i+m] = i;
}
for(int i=1; i<=m; i++){
qu[i] = 1;
}
build(1,n+m,1);
for(int i=1; i<=n; i++){
qu[i] = i+m;
}
for(int i=0; i<m; i++){
scanf("%d",&k);
span[k].second = std::max(span[k].second,query(1,n+m,qu[k],qu[k],1));
span[k].first = 1;
update(1,n+m,idx+1,qu[k],1,1);
qu[k] = idx--;
}
for(int i=1; i<=n; i++){
span[i].second = std::max(span[i].second,query(1,n+m,qu[i],qu[i],1));
printf("%d %d\n",span[i].first,span[i].second);
}
return 0;
}
