题解：P10281 [USACO24OPEN] Grass Segments G

· · 题解

给一个非常傻的大常数单 \operatorname{log} 做法。

考虑我们把左右端点分开进行考虑，我们把一个区间 (l_i,r_i,k_i) 拆分成 (l_i,i) 和 (r_i,i)。我们发现对于一个区间 [l_i,r_i] 来说，能给到其贡献的左端点一定不会超过 r_i，所以我们在每一个右端点处统计答案。

然后我们对于一个区间 [l,r] ，如果区间 [L,R] 能给到其贡献进行分类讨论：

1、对于 L \leq l，显然要满足 l+k \leq R。

2、对于 l < L \leq r-k，则要满足 k \leq R-L。

然后我们就可以开两颗可持久化线段树，分别把 r 和 r-l 挂到对应的 l 上即可。

放一下我丑陋的代码吧。

#include<bits/stdc++.h>
using namespace std;
struct qj{int l,r,k;}a[200005];
struct nod{int p,id;bool tp;}b[400005];
inline nod makeit(int a,int b,int c){nod tmp;tmp.p=a,tmp.id=b,tmp.tp=0;return tmp;}
inline bool cmp(nod x,nod y){return x.p<y.p;}
int num[1200005],T[1200005][2],tot[2];
bool debug;
inline int has(int x){return lower_bound(num+1,num+1+num[0],x)-num;}
struct node{int ls,rs,sum;}tr[1200005<<5][2];
int update(int u,int v,int l,int r,int x,bool op){
    if(!v)v=++tot[op],tr[v][op].ls=tr[v][op].rs=0;
    tr[v][op].sum=tr[u][op].sum;
    if(l==r)return tr[v][op].sum++,v;
    int mid=l+r>>1;
    if(x<=mid)tr[v][op].ls=update(tr[u][op].ls,tr[v][op].ls,l,mid,x,op),tr[v][op].rs=tr[u][op].rs;
    else tr[v][op].rs=update(tr[u][op].rs,tr[v][op].rs,mid+1,r,x,op),tr[v][op].ls=tr[u][op].ls;
    tr[v][op].sum++;
    return v;
}int query(int u,int v,int l,int r,int x,int y,int op){
//  if(debug&&(!op))cout<<l<<" "<<r<<" "<<x<<" "<<y<<" "<<u<<" "<<v<<" "<<tr[v][op].sum<<" "<<tr[u][op].sum<<endl;
    if(x<=l&&r<=y)return tr[v][op].sum-tr[u][op].sum;
    int mid=l+r>>1,ans=0;
    if(x<=mid)ans+=query(tr[u][op].ls,tr[v][op].ls,l,mid,x,y,op);
    if(y>mid)ans+=query(tr[u][op].rs,tr[v][op].rs,mid+1,r,x,y,op);
    return ans;
}int ans[200005],pos[200005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].k);
        b[i*2-1].p=a[i].l,b[i*2-1].id=i,b[i*2-1].tp=0;
        b[i*2].p=a[i].r,b[i*2].id=i,b[i*2].tp=1;
        num[++num[0]]=a[i].l;
        num[++num[0]]=a[i].r;
        num[++num[0]]=a[i].l+a[i].k;
        num[++num[0]]=a[i].r-a[i].k;
        num[++num[0]]=a[i].k;
        num[++num[0]]=a[i].r-a[i].l;
    }sort(num+1,num+1+num[0]);
    num[0]=unique(num+1,num+1+num[0])-num-1;
//  for(int i=1; i<=num[0]; i++)printf("%d\n",num[i]);
    sort(b+1,b+1+n*2,cmp);
    for(int i=1; i<=n*2; i++){
        int id=b[i].id;
//      cout<<b[i].p<<" "<<id<<endl;
        if(!b[i].tp){
            T[i][0]=update(T[i-1][0],T[i][0],1,num[0],has(a[id].r),0);
            T[i][1]=update(T[i-1][1],T[i][1],1,num[0],has(a[id].r-a[id].l),1);
            pos[id]=i;
//          cout<<a[id].r<<endl;
        }else{
            T[i][0]=T[i-1][0],T[i][1]=T[i-1][1];debug=(id==2);
            ans[id]+=query(0,T[pos[id]][0],1,num[0],has(a[id].l+a[id].k),num[0],0);

            ans[id]+=query(T[pos[id]][1],T[upper_bound(b+1,b+1+n*2,makeit(a[id].r-a[id].k,0,0),cmp)-b-1][1],1,num[0],has(a[id].k),num[0],1);
//          cout<<query(0,T[pos[id]][0],1,num[0],has(a[id].l+a[id].k),num[0],0)<<" "<<query(T[pos[id]][1],T[upper_bound(b+1,b+1+n*2,makeit(a[id].r-a[id].k,0,0),cmp)-b-1][1],1,num[0],has(a[id].k),num[0],1)<<endl;
//          cout<<a[id].l+a[id].k<<endl; 
//          cout<<(upper_bound(b+1,b+1+n*2,makeit(a[id].r-a[id].k,0,0),cmp)-b-1)<<endl;
        }
    }
    for(int i=1; i<=n; i++)printf("%d\n",ans[i]-1);
    return 0;
}