BZOJ3236 [AHOI2013] 作业

Description:

Input:

Output:

Sample Input:

3 41 2 21 2 1 31 2 1 11 3 1 32 3 2 3

3 4

1 2 2

1 2 1 3

1 2 1 1

1 3 1 3

2 3 2 3

Sample Output:

2 21 13 22 1

2 2

1 1

3 2

2 1

HINT:

N=100000,M=1000000

题解：

在某处看到的二维数点的例题，然后就去想主席树，想扫描线加线段树什么的。

结果这是个莫队+树状数组的题。。

它在检测我二维数点有没有学傻？？？

/*ID: Sunshine_cfbslPROG: BZOJ3236LANG: C++*/#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int MAXN = 100010;const int MAXM = 1000010;const int Base = 200;int n, m, C[2][MAXN], cnt;int c[MAXN], Hash[MAXN];int a[MAXN], in[MAXN], L, R;int ans1[MAXM], ans2[MAXM];struct Query { int l, r, a, b, ord; bool operator < (const Query &rhs) const { if(in[l] != in[rhs.l]) return in[l] < in[rhs.l]; return r > rhs.r; }}q[MAXM];inline int read() { int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch=='-') ch = getchar(); for(; isdigit(ch); ch = getchar()) x = (x<<1)+(x<<3)+(ch^48); return x * f;}inline int find(int x) { return lower_bound(Hash+1, Hash+cnt+1, x)-Hash;}inline int lowbit(int x) { return x & (-x);}inline void Add(int t, int x, int p) { while(x <= cnt) { C[t][x] += p; x += lowbit(x); }}inline int Query(int t, int x) { int res = 0; while(x) { res += C[t][x]; x -= lowbit(x); } return res;}inline int query(int t, int l, int r) { return Query(t, r)-Query(t, l-1);}int main() { int i; scanf("%d%d", &n, &m); for(i = 1; i <= n; i++) Hash[++cnt] = a[i] = read(); sort(Hash+1, Hash+cnt+1); cnt = unique(Hash+1, Hash+cnt+1)-Hash-1; for(i = 1; i <= n; i++) a[i] = find(a[i]); for(i = 1; i <= n; i++) in[i] = (i-1)/Base+1; for(i = 1; i <= m; i++) { int x; q[i].l = read(), q[i].r = read(); q[i].a = find(read()), q[i].b = find(x = read()); if(Hash[q[i].b] != x) q[i].b--; q[i].ord = i; } sort(q+1, q+m+1); L = 1, R = 0; for(i = 1; i <= m; i++) { while(R < q[i].r) { Add(0, a[++R], 1); if(c[a[R]] == 0) Add(1, a[R], 1); c[a[R]]++; } while(R > q[i].r) { Add(0, a[R], -1); if(c[a[R]] == 1) Add(1, a[R], -1); c[a[R--]]--; } while(L < q[i].l) { Add(0, a[L], -1); if(c[a[L]] == 1) Add(1, a[L], -1); c[a[L++]]--; } while(L > q[i].l) { Add(0, a[--L], 1); if(c[a[L]] == 0) Add(1, a[L], 1); c[a[L]]++; } if(q[i].a > q[i].b) { ans1[q[i].ord] = ans2[q[i].ord] = 0; continue; } ans1[q[i].ord] = query(0, q[i].a, q[i].b); ans2[q[i].ord] = query(1, q[i].a, q[i].b); } for(i = 1; i <= m; i++) printf("%d %d\n", ans1[i], ans2[i]); return 0;}

100

101

102

103

104

105

106

107

108

109

110

111

ID: Sunshine_cfbsl

PROG: BZOJ3236

LANG: C++

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN = 100010;

const int MAXM = 1000010;

const int Base = 200;

int n, m, C[2][MAXN], cnt;

int c[MAXN], Hash[MAXN];

int a[MAXN], in[MAXN], L, R;

int ans1[MAXM], ans2[MAXM];

struct Query {

int l, r, a, b, ord;

bool operator < (const Query &rhs) const {

if(in[l] != in[rhs.l]) return in[l] < in[rhs.l];

return r > rhs.r;

}

}q[MAXM];

inline int read() {

int x = 0, f = 1;

char ch = getchar();

for(; !isdigit(ch); ch = getchar()) if(ch=='-') ch = getchar();

for(; isdigit(ch); ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);

return x * f;

}

inline int find(int x) {

return lower_bound(Hash+1, Hash+cnt+1, x)-Hash;

}

inline int lowbit(int x) {

return x & (-x);

}

inline void Add(int t, int x, int p) {

while(x <= cnt) {

C[t][x] += p;

x += lowbit(x);

}

inline int Query(int t, int x) {

int res = 0;

while(x) {

res += C[t][x];

x -= lowbit(x);

}

return res;

}

inline int query(int t, int l, int r) {

return Query(t, r)-Query(t, l-1);

}

int main() {

int i;

scanf("%d%d", &n, &m);

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

Hash[++cnt] = a[i] = read();

sort(Hash+1, Hash+cnt+1);

cnt = unique(Hash+1, Hash+cnt+1)-Hash-1;

for(i = 1; i <= n; i++) a[i] = find(a[i]);

for(i = 1; i <= n; i++) in[i] = (i-1)/Base+1;

for(i = 1; i <= m; i++) {

int x;

q[i].l = read(), q[i].r = read();

q[i].a = find(read()), q[i].b = find(x = read());

if(Hash[q[i].b] != x) q[i].b--;

q[i].ord = i;

}

sort(q+1, q+m+1);

L = 1, R = 0;

for(i = 1; i <= m; i++) {

while(R < q[i].r) {

Add(0, a[++R], 1);

if(c[a[R]] == 0) Add(1, a[R], 1);

c[a[R]]++;

}

while(R > q[i].r) {

Add(0, a[R], -1);

if(c[a[R]] == 1) Add(1, a[R], -1);

c[a[R--]]--;

}

while(L < q[i].l) {

Add(0, a[L], -1);

if(c[a[L]] == 1) Add(1, a[L], -1);

c[a[L++]]--;

}

while(L > q[i].l) {

Add(0, a[--L], 1);

if(c[a[L]] == 0) Add(1, a[L], 1);

c[a[L]]++;

}

if(q[i].a > q[i].b) {

ans1[q[i].ord] = ans2[q[i].ord] = 0;

continue;

}

ans1[q[i].ord] = query(0, q[i].a, q[i].b);

ans2[q[i].ord] = query(1, q[i].a, q[i].b);

}

for(i = 1; i <= m; i++)

printf("%d %d\n", ans1[i], ans2[i]);

return 0;

}