2019牛客国庆集训派对day3 H

题目链接：H-千万别用树套树

题意：动态插入一维线段端点为 [ l i , r i ] [l_i,r_i] [li​,ri​]，查询给定参数： [ l i , r i ] [l_i,r_i] [li​,ri​]，问有多少条线段可以覆盖它。

我看了一眼感觉CDQ可以写我就写了2333，复杂度是在 O ( n ∗ l o g 2 n ∗ l o g 2 n ) O(n*log_2n*log_2n) O(n∗log2​n∗log2​n)。

首先这个的维度看做三维，时间维，x左端点维，y右端点维，那么如果我们将比较规则定义为时间，然后是x端点从小到大，修改优于查询，那是不是在cdq过程中，遇到左边的修改将y坐标处+1，遇到右边的查询，查询大于等于它的y坐标的数量即可。

于是cdq+树状数组即可解决该题。

当然题目还有一个超级重要的条件，我写完才发现2333，就是查询的时候线段长度不超过3，于是可以直接开三个树状数组，每插入一条线段记录可行左端点即可（差分的形式，第一个可行的位置加，第一个不可行的位置减），所以其实是有一个log的做法的，我菜了。

CDQ分治：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+7;

struct Query{
    int x,y,type,val;
    bool operator <(const Query& z)const{
        if(x!=z.x) return x<z.x;
        return type<z.type;
    }
}query[maxn],temp[maxn];

int sum[maxn];
int n;
void add(int x,int val){
    for(;x;x-=x&-x) sum[x]+=val;
}

int ask(int x){
    int res=0; for(;x<=n;x+=x&-x) res+=sum[x];
    return res;
}
int ans[maxn];
void CDQ(int l,int r){
    if(l==r) return ;
    int mid=(l+r)>>1;
    CDQ(l,mid);
    CDQ(mid+1,r);
    int p=l,q=mid+1,o=0;
    while(p<=mid&&q<=r){
        if(query[p]<query[q]){
            if(query[p].type==1) add(query[p].y,1);
            temp[++o]=query[p++];
        }
        else{
            if(query[q].type==2) ans[query[q].val]+=ask(query[q].y);
            temp[++o]=query[q++];
        }
    }
    while(p<=mid){
        if(query[p].type==1) add(query[p].y,1);
        temp[++o]=query[p++];
    }
    while(q<=r){
        if(query[q].type==2) ans[query[q].val]+=ask(query[q].y);
        temp[++o]=query[q++];
    }

    for(int i=l;i<=mid;++i) if(query[i].type==1) add(query[i].y,-1);
    for(int i=1;i<=o;++i)
        query[i+l-1]=temp[i];
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    //cout<<maxn*log2(maxn)*log2(maxn)<<endl;
    int q,id,x,y,hh;
    while(scanf("%d%d",&n,&q)!=EOF){
        hh=0;
        for(int i=1;i<=q;++i){
            scanf("%d%d%d",&id,&x,&y);
            query[i].type=id,query[i].x=x,query[i].y=y;
            if(id==2) query[i].val=++hh;
        }
        CDQ(1,q);
        for(int i=1;i<=hh;++i){
            printf("%d\n",ans[i]);
            ans[i]=0;
        }
    }

    return 0;
}

           

树状数组：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+7;
int sum[maxn][3];
int maxx=2;
int n;

void add(int x,int val,int id){
    for(;x<=n;x+=x&-x) sum[x][id]+=val;
}

int ask(int x,int id){
    int res=0; for(;x;x-=x&-x) res+=sum[x][id];
    return res;
}

int main(){
    int q,id,l,r;
    while(scanf("%d%d",&n,&q)!=EOF){
        for(int i=1;i<=n;++i) sum[i][0]=sum[i][1]=sum[i][2]=0;
        while(q--){
            scanf("%d%d%d",&id,&l,&r);
            if(id==1)
                for(int i=0;i<=min(maxx,r-l);++i){
                    add(l,1,i),add(r+1-i,-1,i);
                }
            else printf("%d\n",ask(l,r-l));
        }
    }
    return 0;
}