noi.ac #44 链表+树状数组+思维

\(des\)

给出长度为 \(n\) 的序列，全局变量 \(t\)，\(m\) 次询问，询问区间 \([l, r]\) 内出现次数为 \(t\) 的数的个数

\(sol\)

弱化问题：求区间 \([l, r]\) 内只出现一次的数的个数

对于一个右端点 \(r\)，从 \(r\) 向左扫

每次遇到新出现的字符就对该点的点值 +1,

每第二次遇到出现的字符就对该点的点值 -1；

否则不进行任何改变

这样的话，对于区间 \([l, r]\) 内只出现一次的数权值都为 1

线段树或树状数组维护区间加减与区间求和

现在来看这个问题

本质上这两个问题是完全一样的

对于每个右端点 \(r\)

依旧从 \(r\) 向左扫

每遇到第 \(t\) 次出现的字符就对该点的点值 +1，

第 \(t + 1\) 次出现的字符就对该点的点值 -1

实际操作

首先题目不要求在线，这样的话就离线操作

对所有的询问按照右端点进行排序

每个 \(r\) 向前扫时都可以集成上一个 \(r\)

这样的话总的时间复杂度为 \(O(nlogn)\)

今天都快睡着了，没想这题尽然没怎么调试，只调了一下导致死循环的边界

\(code\)

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

#define gc getchar()

#define Rep(i, a, b) for(int i = a; i <= b; i ++)

#define gc getchar()

inline int read() {

	int x = 0; char c = gc;

	while(c < '0' || c > '9') c = gc;

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;

	return x;

}

int n, m, k, t;

int Col[N];

struct Node {

	int l, r, id;

	bool operator < (const Node a) const {

		return this-> r == a.r ? this-> l > a.l : this-> r < a.r;

	}

} Ask[N];

int Nxt[N], Pre[N], Which_t[N], Which_t2[N];

int Js[N], Leftest[N], rightest[N];

int Ans[N];

struct Node_ {

	int Tree[N];

	inline int Lowbit(int x) {return x & -x;}

	void Add(int x, int num) {

		for(; x <= n; x += Lowbit(x)) Tree[x] += num;

	}

	int Calc(int x) {

		if(x == 0) return 0;

		int ret = 0;

		for(; x; x -= Lowbit(x)) ret += Tree[x];

		return ret;

	}

} Bit;

int have_use;

int main() {

	n = read(), m = read(), k = read(), t = read();

	Rep(i, 1, n) Col[i] = read();

	Rep(i, 1, m) {Ask[i].l = read(), Ask[i].r = read(); Ask[i].id = i;}

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

	int L = 1; Ask[1].r + 1;

	Rep(i, 1, m) {

		while(L <= Ask[i].r) {

			Js[Col[L]] ++;

			if(Js[Col[L]] != 1) {

				Pre[L] = rightest[Col[L]];

				Nxt[rightest[Col[L]]] = L;

				rightest[Col[L]] = L;

			}

			if(Js[Col[L]] == 1) {

				rightest[Col[L]] = L;

				Leftest[Col[L]] = L;

			}

			if(Js[Col[L]] == t + 2) {

				Bit.Add(Which_t2[Col[L]], 1);

				Bit.Add(Which_t[Col[L]], -2);

				Bit.Add(Nxt[Which_t[Col[L]]], 1);

				Which_t2[Col[L]] = Which_t[Col[L]];

				Which_t[Col[L]] = Nxt[Which_t[Col[L]]];

				Js[Col[L]] --;

				L ++;

				continue;

			} else if(Js[Col[L]] == t + 1) {

				Bit.Add(Which_t[Col[L]], -2);

				Bit.Add(Nxt[Which_t[Col[L]]], 1);

				Which_t2[Col[L]] = Which_t[Col[L]];

				Which_t[Col[L]] = Nxt[Which_t[Col[L]]];

			} else if(Js[Col[L]] == t) {

				Which_t[Col[L]] = Leftest[Col[L]];

				Bit.Add(Which_t[Col[L]], 1);

			}

			L ++;

		}

		for(int j = have_use + 1; j <= m; j ++) {

			if(Ask[j].r != Ask[have_use + 1].r) {

				have_use = j - 1; break;

			}

			Ans[Ask[j].id] = Bit.Calc(Ask[j].r) - Bit.Calc(Ask[j].l - 1);

			if(j == m) have_use = m;

		}

		i = have_use;

	}

	Rep(i, 1, m) printf("%d\n", Ans[i]);

	return 0;

}

巴特西

noi.ac #44 链表+树状数组+思维

最新文章

热门文章