题解：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

上即可。

放一下我丑陋的代码吧。

CPP

#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;
}

题解：P10281 [USACO24OPEN] Grass Segments G

文章操作

相关推荐

评论

题解：P10281 [USACO24OPEN] Grass Segments G