Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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);
}

{
i = lowb[i];
}

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:

User ID:
Title:

Content: