P3810 3 차원 편차 (길에 꽃 이 핀 다)

11677 단어 데이터 구조
가중치 선분 트 리 세트 평형 트 리 ac 코드
#include
#include
#include
#define mp_ make_pair
#define Pr pair
const int NN=400100;
const int inf=0x3f3f3f3f;
ll n,m,k,x,y,z,q,W,T,N,cnt,tmp,dst,cas,val,tot,num;
//rbtree   ，   pair，rbtree        ， pair second             ，       
tree<Pr,null_type,less<Pr>,rb_tree_tag,tree_order_statistics_node_update> rbt[200100];
pair<int,Pr> a[NN];
int ans[NN];

void update(int i,int val){
	//        
   	for(;i<=k;i+=i&-i) rbt[i].insert(mp_(val,++num));
}

int query(int i,int val){
    int res=0;
    //   
    for(;i;i-=i&-i)res+=rbt[i].order_of_key(Pr(val,++num));
    return res;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //freopen("testdata.txt","r",stdin);
    cin>>n>>k;
    int cnt=1;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second.first>>a[i].second.second;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        update(a[i].second.first,a[i].second.second);
        if(a[i]==a[i+1]) cnt++;
        else ans[query(a[i].second.first,a[i].second.second)]+=cnt,cnt=1;
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<'
';
}
주어진 숫자의 합이 되는 두 숫자가 있는지 확인
데이터 구조 와 알고리즘 기초 - 더 블 링크

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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