QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602149#6701. BaoBao Loves ReadingPonyHexRE 1ms5872kbC++205.0kb2024-09-30 20:16:412024-09-30 20:16:43

Judging History

你现在查看的是最新测评结果

  • [2024-09-30 20:16:43]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5872kb
  • [2024-09-30 20:16:41]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define double long double
#define lc u<<1
#define rc u<<1|1
#define X first
#define Y second
#define endl "\n"
//#define int long long
const int N = 1e5 + 50;
const int M = 2e5 + 5;
const ll maxm = 1e18 + 5;
const ll mod = 998244353;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
//random_shuffle(id + 1, id + n + 1);
ll ksm(ll a, ll b);
ll gcd(ll a, ll b);

template<class T>inline void read(T& x) {
	x = 0;
	char c = getchar();
	while (!isdigit(c))c = getchar();
	while (isdigit(c))x = x * 10 + (c & 15), c = getchar();
}

void write(ll x)
{
	if (x < 0)
		putchar('-'), x = -x;
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
	return;
}


ll a[N], ans[N];
vector<pair<ll, ll> >qu;
ll ne[N];
unordered_map<ll, ll>ex;
unordered_map<ll, ll>pos;

struct node {
	ll val, l, r;
	ll lazy;
}t[N*4];

void pushup(ll u) {
	t[u].val = t[lc].val + t[rc].val;
}

void pushdown(ll u) {
	if (t[u].lazy) {
		t[lc].val += (t[lc].r - t[lc].l + 1)* t[u].lazy;;
		t[lc].lazy += t[u].lazy;
		t[rc].val += (t[rc].r - t[rc].l + 1)* t[u].lazy;;
		t[rc].lazy += t[u].lazy;
		t[u].lazy = 0;
	}
}

void build_ST(ll u, ll l, ll r) {
	t[u].l = l, t[u].r = r;
	t[u].val = 0;
	if (l == r) {
		return;
	}
	ll mid = (l + r) >> 1;
	build_ST(lc, l, mid);
	build_ST(rc, mid + 1, r);
	pushup(u);
}

void modify(ll u, ll x, ll y,ll p) {
	if (x <= t[u].l && t[u].r <= y) {
		t[u].lazy+=p; t[u].val += (t[u].r - t[u].l + 1)*p;
		return;
	}
	pushdown(u);
	ll mid = (t[u].l + t[u].r) >> 1;
	if (x <= mid)modify(lc, x, y,p);
	if (mid < y)modify(rc, x, y,p);
	pushup(u);
}

ll query(ll u, ll x) {
	if (t[u].l==t[u].r) {
		return t[u].val;
	}
	pushdown(u);
	ll mid = (t[u].l + t[u].r) >> 1;
	ll re = 0;
	if (x <= mid)re += query(lc, x);
	else re += query(rc, x);
	pushup(u);
	return re;
}



void solve()
{
	//先理解一下题意,假设现在容量为3,那么我们完全可以以4为区间长度
	//滑动窗口,判断区间内不同的元素的数量,不对,还是要区间长度3来模拟
	//动态出入,走一遍,已知记录队列中不同元素的个数即可
	//比如,当前队列中有3个不同的元素,放入一个元素还是三个
	//这个时候,应该判断3的位置,
	//有点思路,我们遍历走到某个节点的时候,如果见到了元素3
	//元素3会被放到书桌的最上方,判断3,是否会被放回书架在拿回来
	//我们应该判断到下一个3,这段区间内有多少个不同的元素
	//只有不同的元素才会将3不断向后放,
	//ans还会加上数组内不同元素的个数,因为在初次入队的时候,
	//那些元素是从书架上拿下来的
	///想的是对的写的是错的,我们记录的不应该是区间长度
	//我们记录的应该是区间内不同元素的个数,set维护一下应该不会t吧
	ll n; cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i], ex[a[i]] = 1, ans[i] = 0, ne[i] = 0;
	build_ST(1, 1, n);
	//重写一发, 维护区间内不同元素的个数,我有经验,
	//首先应该使,查询升序
	for (int i = 1; i <= n; i++) {
		if (pos[a[i]] == 0) {
			pos[a[i]] = i; continue;
		}
		ne[pos[a[i]]] = i-1;
		qu.push_back({ pos[a[i]],i });
		pos[a[i]] = i;
	}
	sort(qu.begin(), qu.end());

	for (int i = 1; i <= n; i++) {
		//cout << i << " " << ne[i] << endl;
		if (ne[i] == 0) {
			modify(1,i,n,1);
		}
		else {
			modify(1, i, ne[i],1);
		}
	}
	//建树完成,

	//首先一个元素在提供,仅在他在区间之内,且仅持续到离他最近的元素
	//我们,以左区间端点为升序
	ll pr = 1;
	for (auto p = qu.begin(); p != qu.end(); p++) {
		//对于走过的节点,我们消去对后续的影响
		//走到某个节点,要保证之前的节点全部消去
		//
		ll po = p->X;
		for (int i = pr; i <= po; i++) {
			//cout << "kklk" << i << " " << ne[i] << endl;
			if (ne[i] == 0) {
				modify(1, i, n, -1);
			}
			else {
				modify(1, i, ne[i], -1);
			}
		}
		pr = po + 1;
		ll len = 0;
		if(p->Y!=p->X+1)
			len = query(1,p->Y-1);//忘了还有交叉的情况
		//cout << p->X << " " << p->Y << endl;
		//cout << len << endl;
		ans[1]++; ans[len+1]--;
	}
	ll mid = 0;
	for (int i = 1; i <= n; i++) {
		mid += ans[i];
		ans[i] = mid;
	}
	
	cout << ans[1] + ex.size();
	for (int i = 2; i <= n; i++)cout << " " << ans[i] + ex.size();
	cout << endl;
	qu.clear(); ex.clear(); pos.clear();
	return;
}


signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T;
	//read(T);
	while (T--)
		solve();
	return 0;
}

/*PonyHex*/


ll ksm(ll a, ll b) {
	ll base = a;
	ll ans = 1;
	while (b) {
		if (b & 1)ans *= base % mod;
		ans %= mod;
		base *= base; base %= mod;
		b >>= 1;
	}
	return ans % mod;
}
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5872kb

input:

1
7
4 3 4 2 3 1 4

output:

7 6 5 4 4 4 4

result:

ok single line: '7 6 5 4 4 4 4'

Test #2:

score: -100
Runtime Error

input:

100
73
45 45 2 2 2 45 35 45 16 35 16 45 35 2 16 16 45 2 45 45 16 35 35 16 35 35 2 2 2 35 45 35 45 35 16 35 2 2 16 35 16 45 45 16 45 2 16 16 35 16 45 16 45 45 16 16 35 35 35 35 45 45 45 35 16 16 16 2 16 16 35 16 2
83
78 52 7 35 33 82 51 27 45 34 17 51 55 25 26 11 52 41 25 41 13 46 33 83 83 7 40 51 33...

output:

51 30 17 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
80 77 74 73 69 68 66 64 61 61 59 56 53 49 47 47 44 42 39 38 36 36 34 33 30 29 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 2...

result: