HDU – 5372 Segment Game Tree Array

HDU-5372

We consider the total line segment minus the illegal line segment, because it is added to the number axis according to the length from small to large, so the illegal line segment is the number of Rj> Ri plus Lj

Maintenance with a tree array is complete.

#include

#define LL long long

#define LD long double

#define ull unsigned long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair

#define PLI pair

#define PII pair

#define SZ(x) ((int)x.size())

#define ALL(x) (x).begin(), (x).end()

#define fio ios::sync_with_stdio(false); cin.tie(0);



using namespace std;



const int N = 4e5 + 7;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

const double eps = 1e-8;

const double PI = acos(-1);



template<class T, class S> inline < span style="color: #0000ff;">void add(T &a, S b) {a += b; if(a> = mod) a -= mod;}

template<class T, class S> inline < span style="color: #0000ff;">void sub(T &a, S b) {a -= b; if(a < 0) a += mod;}

template<class T, class S> inline < span style="color: #0000ff;">bool chkmax(T &a, S b) {return a true: false;}

template<class T, class S> inline < span style="color: #0000ff;">bool chkmin(T &a, S b) {return a> b? a = b, true: false;}



mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



int n;

int addtot;

int X[N], Xtot;

int ans[N];

int id[N];

int L[N], R[N];

int op[N], b[N];



struct Bit {

 int a[N];

 void init() {

 for(int i = 1; i <= Xtot; i++) {

 a[i] = 0;

}

}

 inline void modify(int x, int v) {

 for(int i = x; i <= Xtot; i += i & -i) {

 a[i] += v;

}

}

 inline int sum(int x) {

 int ans = 0;

 for(int i = x; i; i -= i & -i) {

 ans += a[i];

}

 return ans;

}

 inline int query(int L, int R) {

 if(L> R) return 0;

 return sum(R)-sum(L-1);

}

} bit[2];





void init() {

 Xtot = addtot = 0;

}



int main() {



 int cas = 0;



 while(scanf("%d", &n) != EOF) {

 init();

 int now = 0;

 for(int i = 1; i <= n; i++) {

 scanf("%d%d", &op[i], &b[i]);

 if(!op[i]) {

 addtot++;

 ans[addtot] = now;

 id[i] = addtot;

 L[addtot] = b[i];

 R[addtot] = b[i] + addtot;

 X[++Xtot] = b[i];

 X[++Xtot] = b[i] + addtot;

 now++;

}

 else {

 now--;

}

}

 sort(X + 1, X + 1 +  Xtot);

 Xtot = unique(X + 1, X + 1 + Xtot)-X-1;

 for(int i = 1; i <= addtot; i++) {

 L[i] = lower_bound(X + 1, X + 1  + Xtot, L[i]) - X;

 R[i] = lower_bound(X + 1, X + 1  + Xtot, R[i]) - X;

}



 bit[0].init(); bit[1].init();



 for(int i = 1; i <= n; i++) {

 if(op[i] == 0< span style="color: #000000;">) {

 ans[id[i]] -= bit[0].query(1, L[id[i]]-1);

 ans[id[i]] -= bit[1].query(R[id[i]] + 1, Xtot);

 bit[0].modify(L[id[i]], 1);

 bit[1].modify(R[id[i]], 1);

}

 else {

 bit[0].modify(L[b[i]], -1);

 bit[1].modify(R[b[i]], -1);

}

}



 printf("Case #%d:
 ", ++cas);

 for(int i = 1; i <= addtot; i++) {

 printf("%d
", ans[i]);

}

}

 return 0;

}



/*

*/

#include

#define LL long long

#define LD long double

#define ull unsigned long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair

#define PLI pair

#define PII pair

#define SZ(x) ((int)x.size())

#define ALL(x) (x).begin(), (x).end()

#define fio ios::sync_with_stdio(false); cin.tie(0);



using namespace std;



const int N = 4e5 + 7;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

const double eps = 1e-8;

const double PI = acos(-1);



template<class T, class S> inline < span style="color: #0000ff;">void add(T &a, S b) {a += b; if(a> = mod) a -= mod;}

template<class T, class S> inline < span style="color: #0000ff;">void sub(T &a, S b) {a -= b; if(a < 0) a += mod;}

template<class T, class S> inline < span style="color: #0000ff;">bool chkmax(T &a, S b) {return a true: false;}

template<class T, class S> inline < span style="color: #0000ff;">bool chkmin(T &a, S b) {return a> b? a = b, true: false;}



mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



int n;

int addtot;

int X[N], Xtot;

int ans[N];

int id[N];

int L[N], R[N];

int op[N], b[N];



struct Bit {

 int a[N];

 void init() {

 for(int i = 1; i <= Xtot; i++) {

 a[i] = 0;

}

}

 inline void modify(int x, int v) {

 for(int i = x; i <= Xtot; i += i & -i) {

 a[i] += v;

}

}

 inline int sum(int x) {

 int ans = 0;

 for(int i = x; i; i -= i & -i) {

 ans += a[i];

}

 return ans;

}

 inline int query(int L, int R) {

 if(L> R) return 0;

 return sum(R)-sum(L-1);

}

} bit[2];





void init() {

 Xtot = addtot = 0;

}



int main() {



 int cas = 0;



 while(scanf("%d", &n) != EOF) {

 init();

 int now = 0;

 for(int i = 1; i <= n; i++) {

 scanf("%d%d", &op[i], &b[i]);

 if(!op[i]) {

 addtot++;

 ans[addtot] = now;

 id[i] = addtot;

 L[addtot] = b[i];

 R[addtot] = b[i] + addtot;

 X[++Xtot] = b[i];

 X[++Xtot] = b[i] + addtot;

 now++;

}

 else {

 now--;

}

}

 sort(X + 1, X + 1 +  Xtot);

 Xtot = unique(X + 1, X + 1 + Xtot)-X-1;

 for(int i = 1; i <= addtot; i++) {

 L[i] = lower_bound(X + 1, X + 1  + Xtot, L[i]) - X;

 R[i] = lower_bound(X + 1, X + 1  + Xtot, R[i]) - X;

}



 bit[0].init(); bit[1].init();



 for(int i = 1; i <= n; i++) {

 if(op[i] == 0< span style="color: #000000;">) {

 ans[id[i]] -= bit[0].query(1, L[id[i]]-1);

 ans[id[i]] -= bit[1].query(R[id[i]] + 1, Xtot);

 bit[0].modify(L[id[i]], 1);

 bit[1].modify(R[id[i]], 1);

}

 else {

 bit[0].modify(L[b[i]], -1);

 bit[1].modify(R[b[i]], -1);

}

}



 printf("Case #%d:
 ", ++cas);

 for(int i = 1; i <= addtot; i++) {

 printf("%d
", ans[i]);

}

}

 return 0;

}



/*

*/