Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用线段树和莫队都写了一遍 一定要c输入输出啊

Posted by marszed at 2017-05-18 21:00:40 on Problem 2761
//线段树版本

//#include "stdafx.h"
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define maxn 100010
#define maxm 50010

int n, m;
int input[maxn], lowb[maxn], cop[maxn];

struct in {
	int val, id;
}a[maxn];

int cmp_val(in a, in b)
{
	return a.val < b.val;
}

struct block {
	int id, l, r, k;
}b[maxm];

int cmp(block a, block b)
{
	if(a.l < b.l) return 1;
	if (a.l == b.l&&a.r < b.r) return 1;
	return 0;
}

int cmp_id(block a, block b)
{
	return a.id < b.id;
}

struct Node {
	int l, r, sum;
}cover[maxn << 2];

void build(int rt, int l, int r)
{
	cover[rt].l = l;
	cover[rt].r = r;
	cover[rt].sum = 0;
	if (l == r) return;
	int m = (l + r) >> 1;
	build(rt << 1, l, m);
	build(rt << 1 | 1, m + 1, r);
}

void update(int rt, int val, int flag)
{
	cover[rt].sum += flag;
	if (cover[rt].l == cover[rt].r) return;
	if (val <= cover[rt << 1].r) update(rt << 1, val, flag);
	else update(rt << 1 | 1, val, flag);
}

int query(int rt,int rank)
{
	if (cover[rt].l == cover[rt].r) return cover[rt].l;
	if (cover[rt << 1].sum >= rank) return query(rt << 1, rank);
	return query(rt << 1 | 1, rank - cover[rt << 1].sum);
}

int main()
{
	scanf("%d%d", &n, &m);
	//cin >> n >> m;
	build(1, 1, n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &input[i]);
		//cin >> input[i];
		a[i].val = input[i];
		a[i].id=i;
	}
	sort(a + 1, a + n + 1, cmp_val);
	for (int i = 1; i <= n; i++)
		cop[i] = input[i];
	sort(cop + 1, cop + n + 1);
	for (int i = 1; i <= n; i++)
		lowb[i] = lower_bound(cop + 1, cop + n + 1, input[i]) - cop;
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &b[i].l, &b[i].r, &b[i].k);
		//cin >> b[i].l >> b[i].r >> b[i].k;
		b[i].id = i;
	}
	sort(b + 1, b + m + 1, cmp);
	int pl = 1, pr = 0;
	for (int i = 1; i <= m; i++)
	{
		if (pl < b[i].l)
		{
			for (; pl < b[i].l; pl++)
				update(1, lowb[pl], -1);
		}
		if (pr < b[i].r)
		{
			for (pr++; pr <= b[i].r; pr++)
				update(1, lowb[pr], 1);
		}
		else
		{
			for (; pr > b[i].r; pr--)
				update(1, lowb[pr], -1);
		}
		pr = b[i].r;
		b[i].l = input[a[query(1, b[i].k)].id];
	}
	sort(b + 1, b + m + 1, cmp_id);
	for (int i = 1; i <= m; i++)
		printf("%d\n", b[i].l);
		//cout << b[i].l << endl;
    return 0;
}

//莫队分块版本

/*
#include<cstdio>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define maxn 100010
#define maxm 50010

int n, m, blen;
int input[maxn], cop[maxn], lowb[maxn], sumv[maxn], block[maxn];

struct discrete {
	int val, id;
}dis[maxn];

int cmp_val(discrete a, discrete b)
{
	return a.val < b.val;
}

struct mo_node
{
	int id, l, r, k;
}mo[maxm];

int cmp(mo_node a, mo_node b)
{
	if (a.l / blen < b.l / blen) return 1;
	if (a.l / blen == b.l / blen&&a.r / blen < b.r / blen) return 1;
	return 0;
}

int cmp_id(mo_node a, mo_node b)
{
	return a.id < b.id;
}

void mo_init()
{
	blen = (int)sqrt((double)n);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &mo[i].l, &mo[i].r, &mo[i].k);
		//cin >> mo[i].l >> mo[i].r >> mo[i].k;
		mo[i].id = i;
	}
	sort(mo + 1, mo + m + 1, cmp);
}

void update(int i, int add)
{
	i = lowb[i];
	block[i] += add;
	sumv[i / blen] += add;
}

int main()
{

	ios::sync_with_stdio(false);
	scanf("%d%d", &n, &m);
	//cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &input[i]);
		//cin >> input[i];
		dis[i].val = input[i];
		dis[i].id = i;
	}
	sort(dis + 1, dis + n + 1, cmp_val);
	for (int i = 1; i <= n; i++)
		cop[i] = dis[i].val;
	for (int i = 1; i <= n; i++)
		lowb[i] = lower_bound(cop + 1, cop + n + 1, input[i]) - cop;
	//cout << lowb[2];
	mo_init();
	int pl = 1, pr = 0;
	for (int i = 1; i <= m; i++)
	{
		if (pl < mo[i].l)
		{
			for (; pl < mo[i].l; pl++)
				update(pl, -1);
		}
		else
		{
			for (pl--; pl >= mo[i].l; pl--)
				update(pl, 1);
		}
		pl = mo[i].l;
		if (pr <= mo[i].r)
		{
			for (pr++; pr <= mo[i].r; pr++)
				update(pr, 1);
		}
		else
		{
			for (pr; pr > mo[i].r; pr--)
				update(pr, -1);
		}
		pr = mo[i].r;
		int cnt = 0;
		for (int j = 0; j <= n / blen + 1; j++)
		{
			cnt += sumv[j];
			if (cnt >= mo[i].k)
			{
				cnt -= sumv[j];
				for (int k = j*blen; k < (j + 1)*blen; k++)
				{
					cnt += block[k];
					if (cnt >= mo[i].k)
					{
						mo[i].l = input[dis[k].id];
						break;
					}
				}
				break;
			}
		}
	}
	sort(mo + 1, mo + m + 1, cmp_id);
	for (int i = 1; i <= m; i++)
	{
		printf("%d\n", mo[i].l);
		//cout << mo[i].l << endl;
	}
	return 0;
}

*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator