2025寒假专场朱老师题解

陈甘宇 · 2025-01-23 20:54:21 · 个人记录

第一场

第二场

第三场

第四场

第五场

第六场

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m;
long long a[N];//原序列 
bool vis[N*4];//线段树维护撤销操作 支持区间赋值与单点查询 true表示整个区间要撤销 不用懒标记 true不会变为false  
bool ok[N];//标记每个时刻是否被撤销 

long long b[N];//lsh
int tot_f,tot_che,b_tot;
struct Info{
    int id,op,l,r;
    long long t,k;
}f[N];
struct Node{
    long long t,l,r;
}che[N];

void lsh(){
    sort(b+1,b+1+b_tot);
    int len=unique(b+1,b+1+b_tot)-b-1;
    for(int i=1;i<=tot_f;i++)
        f[i].t=lower_bound(b+1,b+1+len,f[i].t)-b;
    for(int i=1;i<=tot_che;i++)
        che[i].t=lower_bound(b+1,b+1+len,che[i].t)-b,
        che[i].l=lower_bound(b+1,b+1+len,che[i].l)-b,
        che[i].r=lower_bound(b+1,b+1+len,che[i].r)-b;//l r也是时间点  
    b_tot=len;//时间线段树的长度 

//  for(int i=1;i<=tot_f;i++){
//      if(f[i].op==2) 
//          printf("%d %d %lld %d %d\n",f[i].id,f[i].op,f[i].t,f[i].l,f[i].r); 
//      else
//          printf("%d %d %lld %d %d %lld\n",f[i].id,f[i].op,f[i].t,f[i].l,f[i].r,f[i].k); 
//  }
}

bool cmp_che(Node x,Node y){
    return x.t>y.t;
}
void update(int p,int l,int r,int pl,int pr){
    if(vis[p]) return;//小优化 已经集体撤销了 不用再撤销一遍  
    if(l<=pl&&pr<=r){
        vis[p]=true;
        return;
    }
    int mid=(pl+pr)>>1;
    if(l<=mid) update(p<<1,l,r,pl,mid);
    if(r>mid) update(p<<1|1,l,r,mid+1,r);
    vis[p]=vis[p<<1]&&vis[p<<1|1];
}
bool query(int p,int k,int pl,int pr){
    if(vis[p]) return true;
    if(pl==pr) return false;
    int mid=(pl+pr)>>1;
    if(k<=mid) return query(p<<1,k,pl,mid);
    else return query(p<<1|1,k,mid+1,pr);
}
void dfs(int p,int pl,int pr){
    if(vis[p]){
        for(int i=pl;i<=pr;i++)
            ok[i]=true;
        return;
    }
    if(pl==pr) return;
    int mid=(pl+pr)>>1;
    dfs(p<<1,pl,mid);
    dfs(p<<1|1,mid+1,pr);
}
void chexiao(){
    sort(che+1,che+1+tot_che,cmp_che);
    for(int i=1;i<=tot_che;i++){
        if(query(1,int(che[i].t),1,b_tot)==true)//该撤销操作被之前的撤销操作撤销了 
             continue;
        update(1,int(che[i].l),int(che[i].r),1,b_tot);//区间撤销  
    } 
    //遍历整棵树得到每个时间点是否被撤销 记为ok  
    dfs(1,1,b_tot); 
}

bool cmp_f(Info x,Info y){
    return x.t==y.t?x.id<y.id:x.t<y.t;
}
void count_cha(){
    sort(f+1,f+1+tot_f,cmp_f);
    int cnt=0;
    for(int i=1;i<=tot_f;i++)
        if(f[i].op==2&&!ok[int(f[i].t)]) cnt++;
    printf("%d\n",cnt);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++){
        int op;scanf("%d",&op);
        if(op==3){
            ++tot_che;
            scanf("%lld%d%d",&che[tot_che].t,&che[tot_che].l,&che[tot_che].r); 
            b[++b_tot]=che[tot_che].t;
        } 
        else{
            ++tot_f;
            f[tot_f].id=i,f[tot_f].op=op;
            scanf("%lld%d%d",&f[tot_f].t,&f[tot_f].l,&f[tot_f].r); 
            if(op==1) scanf("%lld",&f[tot_f].k); 
            b[++b_tot]=f[tot_f].t; 
        }
    }
    //离散化 
    lsh(); 
    //处理撤销操作 
    chexiao(); 
    //统计未被撤销的查询次数 
    count_cha();
    return 0;
}