## 【BZOJ 4785】[ZJOI 2017] 树状数组

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 30000000;
const int MOD = 998244353;
const int REV = 499122177;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int n,m,tot;
class Segment_Tree{
int cnt,root,AnsTmp,ch[M][2],prod[M][2];
public:
inline void modify(int x, int y, int v, bool t) {
modify(root, 1, n, x, y, v, t);
}
inline int query(int x1, int x2, int y1, int y2, bool t) {
if (x1 > x2 || y1 > y2) return 1;
AnsTmp = 1;
query(root, 1, n, x1, x2, y1, y2, t);
return (AnsTmp+MOD)%MOD;
}
private:
void modify(int &w, int l, int r, int x, int y, int v, bool t) { //X
if (!w) w = ++cnt; modify(prod[w][0], 1, n, y, v, t);
if (l < r) {
int mid = l + r + 1 >> 1;
if (x < mid) modify(ch[w][0], l, mid-1, x, y, v, t);
else modify(ch[w][1], mid, r, x, y, v, t);
}
}
void modify(int &w, int l, int r, int p, int v, bool t) { //Y
if (!w) w = ++cnt, prod[w][0] = prod[w][1] = 1;
prod[w][t] = (LL)prod[w][t] * v % MOD;
if (l < r) {
int mid = l + r + 1 >> 1;
if (p < mid) modify(ch[w][0], l, mid-1, p, v, t);
else modify(ch[w][1], mid, r, p, v, t);
}
}
void query(int w, int l, int r, int L, int R, int y1, int y2, bool t) { //X
if (!w) return;
if (L <= l && r <= R) query(prod[w][0], 1, n, y1, y2, t);
else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0], l, mid-1, L, R, y1, y2, t);
if (mid <= R) query(ch[w][1], mid, r, L, R, y1, y2, t);
}
}
void query(int w, int l, int r, int L, int R, bool t) { //Y
if (!w) return;
if (L <= l && r <= R) AnsTmp = (LL)AnsTmp * prod[w][t] % MOD;
else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0], l, mid-1, L, R, t);
if (mid <= R) query(ch[w][1], mid, r, L, R, t);
}
}
}SGT;

inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t&1) ret=(LL)ret*w%MOD;
return ret;
}

int main() {
for (int i=1,l,r,len,ret;i<=m;i++) {
len = Pow(r-l+1, MOD-2); ++tot;
SGT.modify(l, r, (1 - (len * 2ll)) % MOD, 0);
SGT.modify(l, r, (1 - (len * 4ll)) % MOD, 1);
} else {
ret = (LL)ret * SGT.query(1, l, l, r - 1, 0) % MOD;
ret = (LL)ret * SGT.query(l+1, r, r, n, 0) % MOD;
ret = (LL)ret * SGT.query(1, l, r, n, 1) % MOD;
ret = (ret + 1ll) * REV % MOD;
if (!l&&(tot&1)) ret = (1 - ret) % MOD;
printf("%d\n",(ret+MOD)%MOD);
}
}
return 0;
}


## 【日常小测】传送门

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;

int n,vout,itr[N];
struct Point{int x,y,a,b,mnx,mny,mxx,mxy,v,ori,ch[2];}p[N];
inline bool cmpx(const Point &A, const Point &B) {return A.x < B.x;}
inline bool cmpy(const Point &A, const Point &B) {return A.y < B.y;}
inline bool cmp(const int a, const int b) {return p[a].x < p[b].x || (p[a].x == p[b].x && p[a].y < p[b].y);}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

class KD_Tree{
int root,ans_tmp;
public:
inline void init() {
for (int i=1;i<=n;i++) {
p[i].mnx = p[i].mxx = p[i].x = read();
p[i].mny = p[i].mxy = p[i].y = read();
}
build(root, 1, n, 0);
}
inline void insert(int id, int v) {
insert(root, 1, n, id, v);
}
inline int query(int id) {
ans_tmp = 0;
query(root, 1, n, id, judge(id, root));
return ans_tmp;
}
private:
void build(int &w, int l, int r, bool t) {
if (l == r) w = l;
else if (l < r) {
int mid = l + r >> 1; w = mid;
if (t) nth_element(p+l, p+mid, p+r+1, cmpx);
else nth_element(p+l, p+mid, p+r+1, cmpy);
build(p[w].ch[0], l, mid-1, t^1);
build(p[w].ch[1], mid+1, r, t^1);
for (int i=0,s;i<2;i++) if (s = p[w].ch[i]) {
p[w].mnx = min(p[s].mnx, p[w].mnx);
p[w].mny = min(p[s].mny, p[w].mny);
p[w].mxx = max(p[s].mxx, p[w].mxx);
p[w].mxy = max(p[s].mxy, p[w].mxy);
}
}
}
inline bool Contain(int w, int id) {
if (!w) return 0;
else return p[w].mnx <= p[id].x && p[id].x <= p[w].mxx && p[w].mny <= p[id].y && p[id].y <= p[w].mxy;
}
void insert(int w, int l, int r, int id, int v) {
p[w].v = max(p[w].v, v);
if (l < r) {
int mid = l + r >> 1;
if (Contain(p[w].ch[0], id)) insert(p[w].ch[0], l, mid-1, id, v);
if (Contain(p[w].ch[1], id)) insert(p[w].ch[1], mid+1, r, id, v);
}
}
inline int judge(int i, int j) {
if (p[i].x <= p[j].mnx && p[i].y <= p[j].mny && p[j].mxx <= p[i].a && p[j].mxy <= p[i].b) return 2;
else return max(p[i].x, p[j].mnx) <= min(p[i].a, p[j].mxx) && max(p[i].y , p[j].mny) <= min(p[i].b, p[j].mxy);
}
void query(int w, int l, int r, int id, int ty) {
if (ty == 2) ans_tmp = max(ans_tmp, p[w].v);
else {
if (p[id].x <= p[w].x && p[w].x <= p[id].a && p[id].y <= p[w].y && p[w].y <= p[id].b) ans_tmp = max(ans_tmp, p[w].ori);
int mid = l + r >> 1, tmp;
if (p[w].ch[0] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[0]))) query(p[w].ch[0], l, mid-1, id, tmp);
if (p[w].ch[1] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[1]))) query(p[w].ch[1], mid+1, r, id, tmp);
}
}
}kd;

int main() {
kd.init();
for (int i=1;i<=n;i++) itr[i] = i;
sort(itr+1, itr+1+n, cmp);
for (int j=n,v,i=itr[j];j;i=itr[--j]) {
v = kd.query(i);
kd.insert(i, ++v);
p[i].ori = v;
vout = max(v, vout);
}
printf("%d\n",vout);
return 0;
}


## 【BZOJ 4520】[Cqoi2016] K远点对

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;

struct Point{int x,y;}p[N];
int n,k;
struct CMP{inline bool operator () (const LL A, const LL B){return A>B;}};
priority_queue<LL,vector<LL>,CMP> que;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace KD_Tree{
#define KDT KD_Tree
int MXx[N],MXy[N],MNx[N],MNy[N],ch[N][2],sz[N];
int root,ans_tmp,P; LL LEN;

inline bool cmpx(const Point &A, const Point &B) {return A.x < B.x;}
inline bool cmpy(const Point &A, const Point &B) {return A.y < B.y;}

inline void update(int w){
for (int i=0;i<=1;i++) if (ch[w][i]) {
MXx[w] = max(MXx[w], MXx[ch[w][i]]);
MXy[w] = max(MXy[w], MXy[ch[w][i]]);
MNx[w] = min(MNx[w], MNx[ch[w][i]]);
MNy[w] = min(MNy[w], MNy[ch[w][i]]);
sz[w] += sz[ch[w][i]];
}
}

int build(int l, int r, int ty) {
int mid = l + r >> 1; sz[mid] = 1;
if (ty) nth_element(p+l,p+mid,p+r+1,cmpx);
else nth_element(p+l,p+mid,p+r+1,cmpy);
MXx[mid] = MNx[mid] = p[mid].x;
MXy[mid] = MNy[mid] = p[mid].y;

if (l < mid) ch[mid][0] = build(l,mid-1,ty^1);
if (mid < r) ch[mid][1] = build(mid+1,r,ty^1);
update(mid); return mid;
}inline void build_Tree(){root = build(1,n,1);}

#define Pow(x) ((LL)(x)*(x))
#define DIS(p1,p2) (Pow(p[p1].x-p[p2].x)+Pow(p[p1].y-p[p2].y))

inline LL judge(int w) {
LL ret = 0;
ret += max(Pow(MXx[w]-p[P].x), Pow(MNx[w]-p[P].x));
ret += max(Pow(MXy[w]-p[P].y), Pow(MNy[w]-p[P].y));
return ret;
}

void query(int w) {
LL dw = DIS(w,P), dl = 0, dr = 0;
if (dw > que.top()) que.pop(), que.push(dw);
if (ch[w][0]) dl = judge(ch[w][0]);
if (ch[w][1]) dr = judge(ch[w][1]);

if (dl > dr) {
if (dl > que.top()) query(ch[w][0]);
if (dr > que.top()) query(ch[w][1]);
} else {
if (dr > que.top()) query(ch[w][1]);
if (dl > que.top()) query(ch[w][0]);
}
} inline void Query(const int po){P = po;query(root);}
};

int main(){