codeforces 961 E. Tufurama (주석 트 리)

14955 단어 #의장 수데이터 구조 와 분할 알고리즘데이터 구조
전송 문 주석 트 리 s b sb sb 문제 (%%% 나무 모양 배열 큰 놈 들).간소화 제목: 만족 을 구하 다 x < y, y ≤ a x, x ≤ a y x < y, y \ le ax,x\le a_y x < y, y ≤ ax, x ≤ ay 의 (x, y) (x, y) (x, y) (x, y) 수량.그럼 그냥 주석 트 리 로 제목 을 모 의 하면 됩 니 다.코드:
#include
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const int N=2e5+5;
int n,rt[N],ls[N*30],rs[N*30],siz[N*30],tot=0,a[N];
ll ans=0;
inline void update(int&p,int las,int l,int r,int k){
	p=++tot,ls[p]=ls[las],rs[p]=rs[las],siz[p]=siz[las]+1;
	if(l==r)return;
	int mid=l+r>>1;
	if(k<=mid)update(ls[p],ls[las],l,mid,k);
	else update(rs[p],rs[las],mid+1,r,k);
}
inline int query(int p,int ql,int qr,int l,int r){
	if(ql<=l&&r<=qr)return siz[p];
	int mid=l+r>>1;
	if(qr<=mid)return query(ls[p],ql,qr,l,mid);
	if(ql>mid)return query(rs[p],ql,qr,mid+1,qr);
	return query(ls[p],ql,mid,l,mid)+query(rs[p],mid+1,qr,mid+1,r);
}
int main(){
	freopen("lx.in","r",stdin);
	n=read();
	for(ri i=1;i<=n;++i)a[i]=min(read(),n),ans+=(ll)query(rt[min(a[i],i-1)],i,n,1,n),update(rt[i],rt[i-1],1,n,a[i]);
	cout<<ans;
	return 0;
}
Librdkafka 는 kafka topic - partition 의 관련 데이터 구조 와 조작 에 사용 합 니 다.
벚꽃의 안전한 이동 연결SIM카드 로그인

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage