3809: Gty的二逼妹子序列
Time Limit: 80 Sec Memory Limit: 28 MB
Submit: 1634 Solved: 482
[Submit][Status][Discuss]
Description
Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。
对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便，我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。
Input
第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。
第二行包括n个整数s1...sn(1<=si<=n)。
接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。
保证涉及的所有数在C++的int内。
保证输入合法。
Output
对每个询问，单独输出一行，表示sl...sr中权值∈[a,b]的权值的种类数。
Sample Input
10 10
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4
Sample Output
2
0
0
2
1
1
1
0
1
2
0
0
2
1
1
1
0
1
2
HINT
样例的部分解释：
5 9 1 2
子序列为4 1 5 1 2
在[1,2]里的权值有1,1,2，有2种，因此答案为2。
3 4 7 9
子序列为5 1
在[7,9]里的权值有5，有1种，因此答案为1。
4 4 2 5
子序列为1
没有权值在[2,5]中的，因此答案为0。
2 3 4 7
子序列为4 5
权值在[4,7]中的有4,5，因此答案为2。
建议使用输入/输出优化。
= =，我之前看卿学姐的代码，思考着他的莫队+分块是怎么做的，想着想着就发现暂时不清楚怎么分块，于是打算自己尝试写写看莫队+线段树来更新，然后果然TLE,因为这样的复杂度是O（n^1.5 * logn）
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = 1e5 + ;
const int maxm = + ;
int block, pos[maxn], sz, s[maxn];
struct Point{
int l, r, ca, cb, id;
}q[maxm];
int res[maxm];
bool cmp(Point a, Point b){
if(pos[a.l]==pos[b.l])
return a.r<b.r;
return pos[a.l]<pos[b.l];
}
int n, m;
struct Sedment_tree{
int colorcnt, colornum;
}tree[maxn << ]; inline void push_up(int o){
int lb = o << , rb = o << | ;
tree[o].colornum = tree[lb].colornum + tree[rb].colornum;
} void update(int p, int l, int r, int o, int val){
if (p == l && p == r){
tree[o].colorcnt += val;
if (tree[o].colorcnt == ) tree[o].colornum = ;
if (tree[o].colorcnt == ) tree[o].colornum = ;
return ;
}
int mid = (l + r) / ;
if (p <= mid) update(p, l, mid, o << , val);
if (p > mid) update(p, mid + , r, o << | , val);
push_up(o);
} void add(int x){
update(s[x], , n, , );
} void del(int x){
update(s[x], , n, , -);
} int query(int ql, int qr, int l, int r, int o){
int ans = ;
if (ql <= l && qr >= r){
ans += tree[o].colornum; return ans;
}
int mid = (l + r) / ;
if (ql <= mid) ans += query(ql, qr, l, mid, o << );
if (qr > mid) ans += query(ql, qr, mid + , r, o << | );
return ans;
} int main(){
n = read(), m = read();
sz = sqrt(n);
for (int i = ; i <= n; i++){
s[i] = read();
pos[i] = (i - ) / sz;
}
for (int i = ; i <= m; i++){
q[i].l = read(), q[i].r = read(), q[i].ca = read(), q[i].cb = read();
q[i].id = i;
}
sort(q + , q + + m, cmp);
int L = , R = ;
for (int i = ; i <= m; i++){
while (L > q[i].l){
L--; add(L);
}
while (R < q[i].r){
R++; add(R);
}
while (L < q[i].l){
L++; del(L - );
}
while (R > q[i].r){
R--; del(R + );
}
res[q[i].id] = query(q[i].ca, q[i].cb, , n, );
}
for (int i = ; i <= m; i++){
printf("%d\n", res[i]);
}
return ;
}
（好吧，隔了好久重新看了一下这题，发现是自己傻逼了，应该是可以用线段树的....吧？，具体怎么用的话就是修改一下add和del函数就好了，大致修改的和分块差不多？不过好像最坏情况还是会TLE唉）
因此改为莫队+分块吧
然后思考了一下，我们对于询问区间进行莫队离线操作即可。然后对于修改操作，我们就利用分块来控制颜色区间即可。
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = 1e5 + ;
const int maxm = + ;
int block, pos[maxn], sz, belong[maxn], num, l[maxn], r[maxn], cnt[maxn];
///pos是莫队算法，表示目前这个询问区间是哪个块的
///belong是分块，表示目前这个颜色是属于哪个块的
int s[maxn];
struct Point{
int l, r, ca, cb, id;
}q[maxm];
int res[maxm], color[maxn];
bool cmp(Point a, Point b){
if(pos[a.l]==pos[b.l])
return a.r<b.r;
return pos[a.l]<pos[b.l];
}
int n, m; void build(){
block = sqrt(n); num = n / block;
if (n % block) num++;
for (int i = ; i <= num; i++){
l[i] = (i - ) * block + ; r[i] = i * block;
}
r[num] = n;
for (int i = ; i <= n; i++){
belong[i] = (i - ) / block + ;
}
} void add(int x){
color[x]++;
if(color[x] == ) cnt[belong[x]]++;
} void del(int x){
color[x]--;
if(color[x] == ) cnt[belong[x]]--;
} int query(int x, int y){
int ans = ;
if (belong[x] == belong[y]){
for (int i = x; i <= y; i++) if (color[i]) ans++;
return ans;
}
for (int i = x; i <= r[belong[x]]; i++){
if (color[i]) ans++;
}
for (int i = l[belong[y]]; i <= y; i++){
if (color[i]) ans++;
}
for (int i = belong[x] + ; i < belong[y]; i++)
ans += cnt[i];
return ans;
} int main(){
n = read(), m = read();
sz = sqrt(n);
for (int i = ; i <= n; i++){
s[i] = read();
pos[i] = (i - ) / sz;
}
for (int i = ; i <= m; i++){
q[i].l = read(), q[i].r = read(), q[i].ca = read(), q[i].cb = read();
q[i].id = i;
}
sort(q + , q + + m, cmp);
int L = , R = ;
build();
for (int i = ; i <= m; i++){
while (L > q[i].l){
L--; add(s[L]);
}
while (R < q[i].r){
R++; add(s[R]);
}
while (L < q[i].l){
L++; del(s[L - ]);
}
while (R > q[i].r){
R--; del(s[R + ]);
}
res[q[i].id] = query(q[i].ca, q[i].cb);
}
for (int i = ; i <= m; i++){
printf("%d\n", res[i]);
}
return ;
}
关键：深刻了解莫队算法和分块