1. 离散化+预处理+ min线段树
https://www.luogu.com.cn/problem/CF522D
题意:
给一个 n 个元素的数组 a ,m 次询问,每次询问区间 [ l , r ] 内 数值相等的两个数的最近距离,不存在则输出 -1
思路:
先用 set 和 map 对 a 数组离散化处理,对离散出来的每个点,记录 pos [ i ] 表示数字 i 上一次出现的位置,ans [ i ] 表示 第 i 个数字 离上一个相同位置的距离,nxt [ i ] 表示下一个和第 i 个数字相同的位置
这样就把询问转化为 查询区间 [ l , r ] 内满足 i - ans[ i ] >= l 的最小ans[i],即上一个相同位置也在区间内的最小ans,这里用 min线段树 实现区间最小值查询
然后离线下来每次询问,把所有询问按左端点排序,然后再遍历询问,保证了每次查询的左端点递增,这样 小于 当前询问 l 的数值一定不会在后面的区间里出现,用一个 l 指针维护再也不会查询到的点,每次将 经过的 l 的下一个相同数字处 ans [ nxt [ i ] ] 赋值 INF,表示上一个相同的点不会访问到,这样便可转换为单纯的区间查询,复杂度为(n+q)log(n)
代码:
#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
const int FINF=INT_MIN;
const int INF=INT_MAX;
const int N=5e5+5;
struct node{
int mn;
int l,r;
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs ((p<<1)|1)
}seg[4*N];
int a[N],n,m,ans[N],pos[N],nxt[N];
void build(int p,int l,int r){
seg[p].l=l,seg[p].r=r;
if(l==r){
seg[p].mn=ans[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
seg[p].mn=min(seg[ls].mn,seg[rs].mn);
}
void update(int p,int x,int y){
if(x==0)return;
int l=seg[p].l,r=seg[p].r;
if(l==r){
seg[p].mn=y;
return;
}
if(x<=mid)update(ls,x,y);
else update(rs,x,y);
seg[p].mn=min(seg[ls].mn,seg[rs].mn);
}
int query(int p,int x,int y){
int l=seg[p].l,r=seg[p].r;
if(x<=l&&y>=r){
int ans=seg[p].mn;
return ans;
}
int ans=INT_MAX;
if(x<=mid)ans=min(ans,query(ls,x,y));
if(y>mid)ans=min(ans,query(rs,x,y));
return ans;
}
struct Node{
int x,y,id;
bool operator <(const Node aa)const {
return x<aa.x;
}
}qq[N];
void solve(){
cin>>n>>m;
set<int>ss;
map<int,int>mm;
for(int i=1;i<=n;i++){
cin>>a[i];
ss.insert(a[i]);
}
int cnt=0;
for(auto i:ss){
mm[i]=++cnt;
}
for(int i=1;i<=n;i++)a[i]=mm[a[i]];
for(int i=1;i<=n;i++){
int val=a[i];
if(!pos[val])ans[i]=INT_MAX;
else ans[i]=i-pos[val],nxt[pos[val]]=i;
pos[val]=i;
}
build(1,1,n);
for(int i=1;i<=m;i++){
cin>>qq[i].x>>qq[i].y;
qq[i].id=i;
}
sort(qq+1,qq+m+1);
int l=1;
for(int i=1;i<=m;i++){
int ll=qq[i].x,rr=qq[i].y;
while(l<ll){
if(nxt[l]==0){
l++;
continue;
}
update(1,nxt[l],INT_MAX);
l++;
}
ans[qq[i].id]=query(1,ll,rr);
}
for(int i=1;i<=m;i++){
if(ans[i]==INT_MAX)ans[i]=-1;
cout<<ans[i]<<endl;
}
return;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
// cin>>T;
while(T--){
solve();
}
return 0;
}
2. 线段树维护 线段并
https://ac.nowcoder.com/acm/contest/26896/1005
题意:
有m次操作,每次插入或删除一个线段,或输出 当前所有线段并 的长度
思路:
用一个集合维护当前线段是否存在,线段树维护每个点(小线段)上覆盖的线段个数,每次查询区间 1-n 上被覆盖的点的个数即可
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
const int N=1e5+5;
struct node{
int l,r,flag;
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((l+r)>>1)
}seg[4*N];
void build(int p,int l,int r){
seg[p].l=l,seg[p].r=r;
seg[p].flag=0;
if(l==r)return;
build(ls,l,mid);
build(rs,mid+1,r);
}
void add(int p,int x,int y,int k){
int l=seg[p].l,r=seg[p].r;
if(x<=l&&y>=r){
seg[p].flag+=k;
return;
}
if(x<=mid)add(ls,x,y,k);
if(y>mid)add(rs,x,y,k);
}
int query(int p,int x,int y){
int l=seg[p].l,r=seg[p].r;
if(seg[p].flag){
return r-l+1;
}
if(l==r)return 0;
int ans=0;
if(x<=mid)ans+=query(ls,x,y);
if(y>mid)ans+=query(rs,x,y);
return ans;
}
void solve(){
int n,m;
cin>>m>>n;
build(1,1,n);
map<pii,int>mp;
while(m--){
int u,v,op;
cin>>op>>u>>v;
if(op==1){
if(mp.find(make_pair(u,v))!=mp.end()){
if(mp[make_pair(u,v)]!=0)continue;
}
mp[make_pair(u,v)]=1;
add(1,u,v,1);
}
else if(op==2){
if(mp.find(make_pair(u,v))==mp.end())continue;
if(mp[make_pair(u,v)]==0)continue;
mp[make_pair(u,v)]=0;
add(1,u,v,-1);
}
else cout<<query(1,1,n)<<endl;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
3. 线段树维护等差数列
https://ac.nowcoder.com/acm/contest/26896/1010
题意:
有一个数组 a[N] ,有两个操作,操作1 为 将区间 [ l , r ] 替换成 以 k 为首项,1为公差的等差数列,操作2 为输出区间和
思路:
线段树维护 区间和,打 lazy 标记,表示这一端被替换成了 k 为首项的等差数列
每次 pushdown 的时候,通过区间长度计算出 子区间的首项文章来源:https://www.toymoban.com/news/detail-605109.html
update 的时候,通过 l 和 x 的差值 计算出当前被更改节点 的首项,通过等差数列求和公式直接替换 sum 即可文章来源地址https://www.toymoban.com/news/detail-605109.html
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
const int N=2e5+5;
int a[N];
struct node{
int l,r;
int lazy,sum;
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((l+r)>>1)
}seg[4*N];
void build(int p,int l,int r){
seg[p].l=l,seg[p].r=r;
seg[p].lazy=0;
if(l==r){
seg[p].sum=a[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
seg[p].sum=seg[ls].sum+seg[rs].sum;
}
void pd(int p){
int l=seg[p].l,r=seg[p].r;
int lazy=seg[p].lazy;
if(lazy==0)return;
if(l==r){
seg[p].lazy=0;
return;
}
int len1=mid-l+1,len2=r-(mid+1)+1;
seg[ls].lazy=lazy;
seg[rs].lazy=lazy+len1;
seg[ls].sum=(lazy+lazy+len1-1)*len1/2;
seg[rs].sum=(lazy+len1+lazy+len1+len2-1)*len2/2;
seg[p].lazy=0;
}
void upd(int p,int x,int y,int k){
int l=seg[p].l,r=seg[p].r;
pd(p);
int len=r-l+1;
if(x<=l&&y>=r){
seg[p].lazy=k+l-x;
seg[p].sum=(k+l-x+k+l-x+len-1)*len/2;
return;
}
if(x<=mid)upd(ls,x,y,k);
if(y>mid)upd(rs,x,y,k);
seg[p].sum=seg[ls].sum+seg[rs].sum;
}
int query(int p,int x,int y){
int l=seg[p].l,r=seg[p].r;
pd(p);
if(x<=l&&y>=r){
return seg[p].sum;
}
int ans=0;
if(x<=mid)ans+=query(ls,x,y);
if(y>mid)ans+=query(rs,x,y);
return ans;
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(m--){
int op,x,y,k;
cin>>op>>x>>y;
if(op==1){
cin>>k;
upd(1,x,y,k);
}
else{
cout<<query(1,x,y)<<endl;
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
到了这里,关于线段树题单的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!