【Code Forces】221D - Little Elephant and Array（线段树，思维做法）
/*
确实，这道题需要明白的一点是在于条件的严格，所以，虽然有十万个数，但满足的数最多就450个，在一组数据当中。
所以才采用的方法便是先将数离散化，为了存入结构体数组，这样是为了将个数对应起来，所采用的是map判重以及存储结构体的数组下标。
接下来是遍历结构体数组，找出符合条件的数，条件是该数小于他的个数，这样才有机会满足。
之后只需要遍历这些数在数组中从1开始到某个位置出现的个数即可。
最后做个相减，满足则ans加1
实在妙~
studied from kk303
*/
**#include
**#include
**#include
**#include
线段树做法：更新区间
/*
线段树做法
枚举一个数，并且cnt记录这个数出现的个数。
假如cnt==value（表示这个数）
那么起点在这个数出现第0次到第一次之间取的话就可以将这个数算进去，其余的位置都不行变为0；记这个区间为pre
然后继续向下枚举，假如又找到了一个，那么原来的pre区间就不能够满足了，所以这个区间要置为0
很容易想到，下一个区间可以算，置为1，并更新为pre。整体的一个思路就是通过向右枚举一个数，然后利用线段树更新可满足的起点范围同时将上一个范围置为0。
*/
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
using namespace std;
#define MAX 100005
#define ls rt<<1
#define rs ls|1
#define m (l+r)>>1
int data[MAX];
int sum[MAX << 2];struct pos
{int s, e, id;pos();pos(int _s, int _e, int _id){s = _s;e = _e;id = _id;}bool operator <(const pos b)const{return e < b.e;}
};void ups(int rt)
{if (sum[rt]){sum[ls] += sum[rt];sum[rs] += sum[rt];sum[rt] = 0;}
}void uprt(int rt)
{sum[rt] = sum[ls] + sum[rs];
}
void build(int l, int r, int rt)
{if (l == r){sum[rt] = 0;return;}int mid = m;build(l, mid, ls);build(mid + 1, r, rs);uprt(rt);
}void updata(int L, int R, int c, int l, int r, int rt)
{if (L <= l&&r <= R){sum[rt] += c;return;}ups(rt);int mid = m;if (L <= mid)updata(L, R, c, l, mid, ls);if (mid < R)updata(L, R, c, mid + 1, r, rs);
}int query(int q, int l, int r, int rt)
{if (l == r)return sum[rt];ups(rt);int mid = m;;if (q <= mid)return query(q, l, mid, ls);elsereturn query(q, mid + 1, r, rs);
}
vector q;
vector p[MAX];
int cnt[MAX];
pairpre[MAX];
int ans[MAX];
int main()
{int n, k;scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++){scanf("%d", &data[i]);if (data[i] > n)data[i] = 0;}int a, b;for (int i = 0; i < k; i++){scanf("%d%d", &a, &b);q.push_back(pos(a, b, i));}build(1, n, 1);sort(q.begin(), q.end());int num = 0;memset(cnt, 0, sizeof(cnt));for (int j = 1; j <= n; j++){int value = data[j];if (value){cnt[value]++;p[value].push_back(j);if (cnt[value] == value){pre[value] = make_pair(1, p[value][0]);updata(1, p[value][0], 1, 1, n, 1);}elseif (cnt[value] > value){updata(pre[value].first, pre[value].second, -1, 1, n, 1);pre[value] = make_pair(pre[value].second + 1, p[value][cnt[value] - value]);updata(pre[value].first, pre[value].second, 1, 1, n, 1);}}while (num < k&&q[num].e == j){ans[q[num].id] += query(q[num].s, 1, n, 1);num++;}}for (int i = 0; i < k; i++)printf("%d\n", ans[i]);
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！