2021-04-03

2020 ACM-ICPC, Asia Kunming Regional

字数统计: 5.3k字 | 阅读时长: 26分

solved	A	B	C	D	E	F	G	H	I	J	K	L	M
5 / 13	·	·	Ø	·	·	·	Ø	Ø	O	Ø	O	Ø	O

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

Tryna: 几何题的细节没处理好，总得来说就是题写得还不够多，没有碰到这种情况。

lllllan-个人反思

我场上的问题：

染色那题。虽然很快找到了解题方向，但是因为自己代码能力太弱，自己写不出来，不能帮大家分担压力。

赛时后半段。那道几何体其实我就是帮不上什么忙了，我应该去读题或者想别的题目，自己选择上的失误，导致后半段我零作用，游离于赛场之外。真的抱歉。

没有想到八百人的比赛出现了严重的歪榜，没有读完所有题目导致失去了一些简单题。这个我责任比较大，因为今天我的可做题比较少，我应该去做这个读题的工作。

我场下的问题：

我不是第一次爆零了。还是因为自己的刷题不够，知识面不够，每次的可做题都不算多，也经常有找到解题方向但是不会写的题目。是我自己训练强度不够个人实力太弱的原因。

我暂时的个人训练计划：

实验室安排的省赛训练补题，除了补出自己本来负责的范围，还要去补一题自己接触比较少的题型，算是知识面的一个扩充（如果内容比较多，会先记着，留到暑假进行补习）

cf不能再落下。正常时间的比赛不能再找借口逃掉，虽然晚上的脑子不一定是最清醒的状态，但是有比赛的刺激也许更能促进思考。除了比赛还要去刷以往的题目，算是一些简单题的代码能力上的锻炼和各种题型的熟悉。

其他算法的一些学习我想可能留到暑假，抽一个较长较集中的时间系统学一下。

谢谢哥哥们今天的发挥，我会处理好自己的不足，增强个人实力来帮助大家，希望下次比赛都能各司其职，取得一个满意的成绩

比赛链接

C. Cities

题意：
现有 $n$ 个城镇和 $n$ 个国王，刚开始第 $i$ 个城镇属于第 $a_i$ 个国王。现在每次可以选一个下标连续且属于同一国王的城镇，将这些城镇归属到任意一个国王下面，问让所有城镇都属于一个国王，最少需要多少次这样的操作。

思路：
区间合并，试试看能否用区间 $dp$ 进行操作。每次选取的区间肯定是越长越好，那么我们刚开始就把连续的，属于同一个国王的城镇区间缩成一个点。为了让能选的区间变得更长，要贪心地往左右区间合并。这时我们发现，如果左右区间的所属国王是相同的，那么我们只要修改中间这个区间的城镇，就能得到一个更长的区间。其余的就没区别了。那么我们预处理出每个区间的前一段和它属于同一个国王的区间在哪里，就能对这个区间进行状态转移了。

同时，我们这里是向前找上一个和最后的点相同的区间，所以对于所有的区间，我们都把它想象成向右合并的，才能得到最优解。

例如，对于 $1232$ 这个区间，我们在进行合并的时候， $[1, 2]$ 区间合并后当成属于第二个国王，那么我们从 $[3, 4]$ 往前找的时候，只用修改第三个城镇属于第二个国王，就能让所有城镇都一样了。

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 7;

int dp[N][N];
int n, m;
int a[N], pre[N], lst[N];

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        pre[i] = 0;
        lst[i] = 0;
    }
    m = 1;
    for (int i = 2; i <= n; ++i) {
        while (i <= n && a[i] == a[i - 1]) {
            i++;
        }
        if (i > n) break;
        a[++m] = a[i];
    }
    n = m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = 0;
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        pre[i] = lst[ a[i] ];
        lst[ a[i] ] = i;
    }

    for (int len = 1; len < n; ++len) {
        for (int i = 1; i <= n; ++i) {
            int j = i + len;
            if (j > n) break;
            dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
            for (int k = pre[j]; k >= i; k = pre[k]) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j - 1] + 1);
            }
        }
    }
    printf("%d\n", dp[1][n]);
}

int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}

G. Gift

题意：
假设现在是 $2021$ 年的第一天。你有 $n$ 个朋友， $m$ 个可购买的礼物，以及 $w$ 元。给出每个朋友的生日、你亲手为他们制作礼物的时间以及你亲手制作礼物能得到的好感度。你每天只能进行一种礼物的制作，但可以不连续制作同一个礼物。当然，你也可以选择直接购买礼物，花费 $a_i$ 元，对于任何一个朋友，都能获得 $b_i$ 好感度，但每个礼物只能购买一次。每个人都只能在生日当天收一次礼物，问你今年能收获的最大好感度是多少。

思路：
想不到好的贪心，题面也有点像背包，那么考虑 $dp$ 。考虑他给出的各项参数，发现 $O(365 * N * M * T)$ 差不多能符合 $1s$ 的时限。生日是有先有后的，我们要符合递推的顺序。所以我们记录下每个人生日距离 $1$ 月 $1$ 日的天数，以天数为关键字进行升序排序，同时第一维也可以降下来。 $dp[i][j]$ 代表花费 $i$ 天制作礼物，买了 $j$ 个礼物后，能获得的最大好感度。写的时候发现买礼物时，并不好决定当下买哪个礼物，那么我们预处理一下，用状压处理出买对应数量礼物时，能获得的最大好感度，在最后找答案的时候加上去就行了。注意背包的两维要从后往前，避免重复送礼物。最后还要注意 $2$ 月 $29$ 的情况，因为 $2021$ 年不是闰年，要直接不管这一天。~~一直想知道这天过生日的是4年过一次吗（逃~~

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e2 + 7;

struct Fir{
    int d, c, v;

    Fir () {}
    Fir (int d, int c, int v) : d(d), c(c), v(v) {}

    bool operator < (const Fir & f) const {
        return d < f.d;
    }
}fir[N];

int n, m, w;
int a[17], b[17];
int dp[371][17];
int add[17];
int pre[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

void solve() {
    memset(dp, -0x3f, sizeof(dp));
    memset(add, 0, sizeof(add));
    scanf("%d %d %d", &n, &m, &w);
    int tot = 0;
    for (int i = 1; i <= n; ++i) {
        int yy, mm, dd, cc, vv;
        scanf("%d-%d-%d %d %d", &yy, &mm, &dd, &cc, &vv);
        if (mm == 2 && dd == 29) continue;
        tot++;
        fir[tot] = Fir(pre[mm - 1] + dd, cc, vv);
    }
    sort(fir + 1, fir + 1 + tot);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &a[i], &b[i]);
    }
    int ed = 1 << m;
    for (int i = 1; i < ed; ++i) {
        int cost = 0;
        int val = 0;
        int num = 0;
        int sta = i;
        for (int j = 1; j <= m; ++j) {
            if (sta & 1) cost += a[j], val += b[j], num++;
            sta >>= 1;
        }
        if (cost <= w) add[num] = max(add[num], val);
    }
    dp[0][0] = 0;
    for (int i = 1; i <= tot; ++i) {
        for (int j = 365; j >= 0; --j) {
            for (int k = m; k >= 0; --k) {
                if (k + 1 <= m) dp[j][k + 1] = max(dp[j][k + 1], dp[j][k]);
                if (j + fir[i].c <= 365 && j + fir[i].c <= fir[i].d) { // 这里注意判断下之前的天数够不够，不够的话是不能赶在生日当天送礼物的
                    dp[j + fir[i].c][k] = max(dp[j + fir[i].c][k], dp[j][k] + fir[i].v);
                }
            }
        }
    }
    int ans = -inf;
    for (int i = 1; i <= 365; ++i) {
        for (int j = 0; j <= m; ++j) {
            ans = max(ans, dp[i][j] + add[j]);
        }
    }
    printf("%d\n", ans);
}

int main() {
    for (int i = 1; i <= 12; ++i) pre[i] += pre[i - 1];
    int t = 1;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}

H - Hard Calculation

solved by Tryna. 00:02(+)

AC代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    cout<<n + 2020<<endl;
}

I - Mr. Main and Windmills

solved by Tryna.(-)

题意： 你坐着火车从城市 $s$ 到城市 $t$ ，路线是一条直线。在这条路的一侧有若干个风车，当你在移动时，风车 $A$ 和风车 $B$ 的相对位置会发生改变，求风车 $h$ 改变了 $k$ 次后你当前的位置。

题解： 一道很简单的几何题，但是精度没处理好导致比赛时没能出来。思路就是枚举所有风车，求他们在线段 $st$ 上的交点，然后排个序，就可以O(1)查找了。主要的问题就是判断点是否在线段上时，得省去向量共线的判断，因为交点肯定在直线上，因为求交点就已经是个损失精度的操作了，再重复判断一下，可能就会炸了。几何题还是有太多细节了。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
const double eps = 1e-8;
int sgn(double x) {
	if(fabs(x) < eps) return 0;
	if(x < 0) return -1;
	return 1;
}
struct Point{
	double x, y;
	Point(){}
	Point(double _x, double _y) {
		x = _x;
		y = _y;
	}
	Point operator - (const Point &b) const{
		return Point(x - b.x, y - b.y);
	}
	double operator ^ (const Point &b) const{
		return x * b.y - y * b.x;
	}
	double operator * (const Point &b)const{
		return x * b.x + y * b.y;
	}
	double distance(Point p) {
		return hypot(x - p.x, y - p.y);
	} 
}P[maxn], st, ed;
struct Line{
	Point s, e;
	Line(){}
	Line(Point _s, Point _e) {
		s = _s;
		e = _e;
	}
	bool pointonset(Point p) {
		return sgn((p - s) * (p - e)) <= 0;
	}
	int relation(Point p) {
		int c = sgn((p - s) ^ (e - s));
		if(c < 0) return 1;
		else if(c > 0) return 2;
		else return 3;
	}
	bool parallel(Line v) {
		return sgn((e - s) ^ (v.e - v.s)) == 0;
	}
	int linecrossline(Line v) {
		if((*this).parallel(v))
			return v.relation(s) == 3;
		return 2;
	}
	Point crosspoint(Line v) {
		double a1 = (v.e - v.s) ^ (s - v.s);
		double a2 = (v.e - v.s) ^ (e - v.s);
		return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));
	}
};
bool cmp(Point a, Point b) {
	double d1 = st.distance(a);
	double d2 = st.distance(b);
	return d1 < d2;
}
int n, m;
vector<Point>G[maxn];
void solve() {
	scanf("%d %d", &n, &m);
	scanf("%lf %lf %lf %lf", &st.x, &st.y, &ed.x, &ed.y);
	for(int i = 1; i <= n; i++)
		scanf("%lf %lf", &P[i].x, &P[i].y);
	Line l = Line(st, ed);
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			Line l1 = Line(P[i], P[j]);
			if(l.linecrossline(l1) != 2) continue;
			Point pp = l.crosspoint(l1);
			if(l.pointonset(pp) == 1) {
				G[i].push_back({pp.x, pp.y});
				G[j].push_back({pp.x, pp.y});
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		sort(G[i].begin(), G[i].end(), cmp);
	}
	while(m--) {
		int h, k;
		scanf("%d %d", &h, &k);
		if(G[h].size() < k)
			puts("-1");
		else printf("%.10f %.10f\n", G[h][k - 1].x, G[h][k - 1].y);
	}
}

int main() {
	solve();
	return 0;
}

J. Parallel Sort

Solve by Sstee1XD & lllllan. 2:57(+)

题意： 给你 $1~n$ 的排列，你每次可以选择k个二元组，让各个元组中的两个数交换位置，问你最少需要换几次让序列有序。

思路： 观察得从一个不在正确位置的数字开始，可以形成一个环。对于每个环而言，我们可以交换 $(2, n)(3, n - 1)\dots$ 这些位置的值，最后一步暴力换就行了。每个环又是相互独立的，所以最多需要两步。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;

int a[N], pos[N];
int vis[N];
vector<pair<int, int>> v1, v2;
vector<int> g[N];
int tot;
int nxt[N];
bool good[N];

void work(int i, int j) {
	swap(a[i], a[j]);
	swap(pos[a[i]], pos[a[j]]);
}

int main() {
	int n;
	scanf("%d", &n);
	memset(nxt, -1, sizeof(nxt));
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		pos[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue;
		if (a[i] == i) {
			vis[i] = 1;
			continue;
		}
		int tmp = i;
		tot++;
		g[tot].push_back(i);
		while (!vis[tmp]) {
			vis[tmp] = 1;
			tmp = pos[tmp];
			g[tot].push_back(tmp);
		}
	}
	if (!tot) {
		puts("0");
		return 0;
	}
	int ans = 1;
	for (int i = 1; i <= tot; ++i) {
		if (g[i].size() == 2) {
			v1.push_back({g[i][0], g[i][1]});
			work(g[i][0], g[i][1]);
			continue;
		}
		for (int j = 1, k = g[i].size() - 1; j < k; j++, k--) {
			v1.push_back({g[i][j], g[i][k]});
			work(g[i][j], g[i][k]);
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (!good[i] && pos[i] != i) {
			ans = 2;
			v2.push_back({i, pos[i]});
			good[i] = good[pos[i]] = true;
		}
	}
	printf("%d\n", ans);
	if (v1.size()) printf("%d", v1.size());
	for (int i = 0; i < v1.size(); ++i) {
		printf(" %d %d", v1[i].first, v1[i].second);
	}
	puts("");
	if (v2.size()) printf("%d", v2.size());
	for (int i = 0; i < v2.size(); ++i) {
		printf(" %d %d", v2[i].first, v2[i].second);
	}
	return 0;
}

K. Riichi!!

题意：
现有14张牌，现在进行一次舍张和进张，输出能胡牌的方案。

思路：

因为每种牌型都是相互独立的，所以我们可以先求出所有合法的情况。在存拥有的牌的情况时，由于数据很小，我们可以用二进制存储，大概长这样。

$1$ (大小为 $1$ 的牌的数量) $1$ (大小为 $2$ 的牌的数量) $1\dots1$ (大小为 $9$ 的牌的数量)

中间直接留对应数量的大小即可，完全不会太大。注意字牌没有顺子，额外处理下就行。

然后暴力枚举舍张和进张，连下答案即可。

AC代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1 << 25;

bool vis[N];
char a[] = {"wbsz"};
int cur[11], num[37];
int id[303];
int tot, cnt;
string s;
string ans[37];

void add(int p, int v) {
    cur[p] += v;
    tot += v;
}

void addAns(int pos, int i) {
    int v = i % 9;
    if (v == 0) v = 9;
    ans[pos] += to_string(v);
    if (i <= 9) ans[pos] += "w";
    else if (i <= 18) ans[pos] += "b";
    else if (i <= 27) ans[pos] += "s";
    else ans[pos] += "z";
}

int getHash() {
    int res = 0;
    cnt = 0;
    for (int i = 1; i <= 9; ++i) {
        res <<= 1;
        res += 1;
        res <<= cur[i];
        cnt += cur[i];
    }
    return res;
}

void dfs(int p) {
    int now = getHash();
    if (vis[now]) return;
    vis[now] = true;
    while (p <= 9) {
        if (p <= 7 && tot <= 11) { // shunzi
            add(p, 1); add(p + 1, 1); add(p + 2, 1);
            dfs(p);
            add(p, -1); add(p + 1, -1); add(p + 2, -1);
        }
        if (tot <= 11) { // kezi
            add(p, 3);
            dfs(p);
            add(p, -3);
        }
        if (tot <= 12 && tot % 3 == 0) { // quetou
            add(p, 2);
            dfs(p);
            add(p, -2);
        }
        p++;
    }
}

bool check() {
    int quetou = 0;
    for (int i = 0; i <= 2; ++i) {
        memcpy(cur + 1, num + 9 * i + 1, sizeof(cur));
        if (!vis[getHash()]) return false;
        quetou += cnt % 3 == 2;
    }
    int d = 27;
    for (int i = 1; i <= 7; ++i) {
        if (num[d + i] % 3 == 1) return false;
        quetou += num[d + i] % 3 == 2;
    }
    return quetou == 1;
}

void solve() {
    memset(num, 0, sizeof(num));
    cin >> s;
    for (int i = 0; i < 14; ++i) {
        int n = s[i * 2] - '0';
        char c = s[i * 2 + 1];
        num[id[c] + n]++;
    }
    if (check()) {
        cout << "Tsumo!" << endl;
        return;
    }
    for (int i = 1; i <= 34; ++i) {
        ans[i] = "";
    }
    int ansNum = 0;
    for (int i = 1; i <= 34; ++i) {
        addAns(i, i);
        ans[i] += " ";
        if (num[i]) {
            int flag = 0;
            num[i]--;
            for (int j = 1; j <= 34; ++j) {
                num[j]++;
                if (check()) {
                    flag = 1;
                    addAns(i, j);
                }
                num[j]--;
            }
            ansNum += flag;
            num[i]++;
        }
    }
    cout << ansNum << endl;
    for (int i = 1; i <= 34; ++i) {
        if (ans[i].length() > 3) {
            cout << ans[i] << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
    for (int i = 0; i < 4; ++i) {
        id[ a[i] ] = i * 9;
    }
    dfs(1);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

L. Simone and graph coloring

Solved by Sstee1XD & lllllan. 0:53(+)

题意： 给你 $1$ ~ $n$ 的排列，你需要对每一个点进行染色，相同颜色的点取出来之后，他们的值要求递增，问你最少需要几种颜色，以及染色的方案。

思路： 想要颜色最少，我们会贪心地去找之前比当前值小的，并且最接近当前值的一个值。我们思考一下贪心的正确性，如果我们选择不让当前值并到之前的值里，让它独立出来，效果其实是一样的。那么我们只需要维护一个递增的序列，在里面二分即可。我们的方法只会在序列前面插入值，将第一个值插入到序列的最后一个位置，进行维护即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
int n, a[maxn], res[maxn], cor[maxn], cc[maxn];
int R, L;
int tot;
void solve() {
	tot = 1;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	R = n;
	L = n;
	res[n] = a[1];
	cc[a[1]] = tot;
	cor[1] = tot;
	for (int i = 2; i <= n; ++i) {
		int l = L, r = R, mid;
		int ans = -1;
		while (l <= r) {
			int mid = l + r >> 1;
			if (res[mid] <= a[i]) ans = mid, l = mid + 1;
			else r = mid - 1;
		}
		if (ans != -1) {
			cor[i] = cc[res[ans]];
			cc[a[i]] = cor[i];
			res[ans] = a[i];
		} else {
			L = L - 1;
			res[L] = a[i];
			cor[i] = ++tot;
			cc[a[i]] = cor[i];
		}
	}
	printf("%d\n", tot);
	for (int i = 1; i <= n; ++i) {
		printf("%d%c", cor[i], " \n"[i == n]);
	}
}

int main() {
	int t = 1;
	scanf("%d", &t);
	while(t--)
		solve();
	return 0;
}

M. Stone Games

Solved by Sstee1XD. (-)

题意： 询问区间 $mex$ ，强制在线。

思路： 考虑对于一个区间，我们想要求得 $mex$ ，可以对这个区间进行升序排序。当第一个数字不为 $1$ 时，答案就是 $1$ 。设当前前缀和为 $x$ ，那么我们前面的区间我们可以得到 $[1, x]$ 之间任意一个数字，设当前数字为 $y$ ，我们将 $y$ 并入之前的区间，可以得到 $[y, y + x]$ 之间的任意一个数字。当 $y \leq x$ 时，这个前缀和就可以延展；如果 $y > x$ ，那么此时就可以得到 $mex$ 为 $x + 1$ 。对于上述思路，我们可以用主席树来维护，一直询问更新前缀和 $sum$ ，然后再询问区间内所有 $\leq sum + 1$ 的数字的和。如果这个和并没有比 $sum$ 大，那么 $mex$ 即为 $sum+1$ 。时间复杂度看似很大，但最坏情况下 $sum$ 是以以 $1$ 为首项，以 $1$ 为公差的等差数列求和的增长速率增长的，是比较快的。

AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7;

int n, q, li, ri, k;
int a[N], rt[N];

struct Hash{
	int a[N];
	void init() {
		*a = 0;
	}
	void add(int v) {
		a[++*a] = v;
	}
	int size() {
		return *a;
	}
	void gao() {
		sort(a + 1, a + 1 + *a);
		*a = unique(a + 1, a + 1 + *a) - a - 1;
//		cout << *a << endl;
	}
	int get(int v) {
		return lower_bound(a + 1, a + 1 + *a, v) - a;
	}
	int rget(int v) {
		return a[v];
	}
}hs;

struct Seg{
	struct Node{
		int ls, rs, cnt;
		void init() {
			ls = rs = cnt = 0;
		}
	}t[N * 50];
	int tot;
	void init() {
		tot = 0;
		t[tot].init();
	}
	int newnode() {
		t[++tot].init();
		return tot;
	}
	void build(int &id, int l, int r) {
		if (!id) id = newnode();
		if (l == r) {
			return;
		}
		int mid = l + r >> 1;
		build(t[id].ls, l, mid);
		build(t[id].rs, mid + 1, r);
	}
	void modify(int &rt, int l, int r, int pos, int v) {
		int now = newnode();
		t[now] = t[rt];
		t[now].cnt += v;
		if (l == r) {
			rt = now;
			return;
		}
		int mid = l + r >> 1;
		if (pos <= mid) {
			modify(t[now].ls, l, mid, pos, v);
		} else {
			modify(t[now].rs, mid + 1, r, pos, v);
		}
		rt = now;
	}
	int query(int lr, int rr, int l, int r, int k) {
		if (l == r) return l;
		int mid = l + r >> 1;
		int lcnt = t[ t[lr].ls ].cnt, rcnt = t[ t[rr].ls ].cnt;
		if (rcnt - lcnt >= k) return query(t[lr].ls, t[rr].ls, l, mid, k);
		else return query(t[lr].rs, t[rr].rs, mid + 1, r, k - (rcnt - lcnt));
	}
}seg;

int main() {
	scanf("%d%d", &n, &q);
	hs.init();
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), hs.add(a[i]);
	hs.gao();
	int m = hs.size();
	seg.init();
	rt[0] = 0;
	seg.build(rt[0], 1, m);
	for (int i = 1; i <= n; ++i) {
		rt[i] = rt[i - 1];
		seg.modify(rt[i], 1, m, hs.get(a[i]), 1);
	}
	for (int i = 1; i <= q; ++i) {
		scanf("%d%d%d", &li, &ri, &k);
		printf("%d\n", hs.rget(seg.query(rt[li - 1], rt[ri], 1, m, k)));
	}
	return 0;
}