CVJETICI - Cvjetici
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
#include<queue>
#define MAX 100100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
int tree[MAX<<2];
ii a[MAX];
int n;
void init(void) {
scanf("%d",&n);
FOR(i,1,n) {
scanf("%d",&a[i].fi);
scanf("%d",&a[i].se);
}
}
void pushdown(int i) {
tree[2*i]+=tree[i];
tree[2*i+1]+=tree[i];
tree[i]=0;
}
void update(int i,int l,int r,int u,int v,int val) {
if (l>v) return;
if (r<u) return;
if (l>r) return;
if (v<u) return;
if (u<=l && r<=v) {
tree[i]+=val;
return;
}
pushdown(i);
int m=(l+r)/2;
update(2*i,l,m,u,v,val);
update(2*i+1,m+1,r,u,v,val);
}
int get(int u) {
int i=1;
int l=1;
int r=100000;
while (true) {
if (l==r) {
int tmp=tree[i];
tree[i]=0;
return (tmp);
}
pushdown(i);
int m=(l+r)/2;
if (m<u) {
i=2*i+1;
l=m+1;
}
else {
i=2*i;
r=m;
}
}
}
void process(void) {
FOR(i,1,n) {
printf("%d\n",get(a[i].fi)+get(a[i].se));
update(1,1,100000,a[i].fi+1,a[i].se-1,1);
}
}
int main(void) {
init();
process();
return 0;
}