WA on#7求助
查看原帖
WA on#7求助
995117
pineappler楼主2024/5/20 20:22
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,Num=N*40;
int root[N],idx;
int a[N];
struct Node{
	int l,r,ls,rs,sum;
}tr[Num];
void pushup(int u){
	tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
}
void build(int &u,int l,int r){
	u=++idx;
	tr[u].l=l;tr[u].r=r;
	if(l==r) return;
	int mid=l+r>>1;
	build(tr[u].ls,l,mid);
	build(tr[u].rs,mid+1,r);
}
void insert(int &u,int v,int x){
	u=++idx;
	int l=tr[v].l,r=tr[v].r;
	tr[u].l=l;tr[u].r=r;
	if(l==x && r==x){
		tr[u].sum = tr[v].sum + 1;
	}else{
		int mid=l+r>>1;
		if(x<=mid){
			tr[u].rs=tr[v].rs;
			insert(tr[u].ls,tr[v].ls,k);
		}else{
			tr[u].ls=tr[v].ls;
			insert(tr[u].rs,tr[v].rs,k);
		}
		pushup(u);
	}
}
int query(int u,int l,int r){
	if(l<=tr[u].l && tr[u].r<=r){
		return tr[u].sum;
	}else{
		int mid=tr[u].l+tr[u].r>>1,ans=0;
		if(l<=mid) ans+=query(tr[u].ls,l,r);
		if(mid<r) ans+=query(tr[u].rs,l,r);
		return ans;
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>n) a[i]=n;
	}
	build(root[0],1,n);
	for(int i=1;i<=n;i++){
		insert(root[i],root[i-1],a[i]);
	}
	long long ans=0;
	for(int i=2;i<=n;i++){
		long long x=query(root[min(i-1,a[i])],i,n);
		ans += x;
	}
	printf("%d",ans);
	return 0;
}
2024/5/20 20:22
加载中...