Think: 因为要满足题意，所以优先 采用单调栈来进行解题。 这是春节的题目 2333， 然后半年过去了， 才写解题报告（手动滑稽）。 我的思路就是 建立结构体来储存 威胁数， 然后利用单调栈的特性来进行计算 威胁数， 进而储存。 输出时，输出相对应的a[key].cnt值即可~~
主要坑点：战力相同的情况要忽略， 反正 我 WA了3发都是这个原因
Problem Description
Re0 虽然是老套的穿越剧情，但是却有着虐男主 (486) 的新奇点子。作为 2016 最火的番，我们来统计一下其中每个人能看到的对手的人数吧。 对于当前的人，他只能看见战力从他依次增高的一个阶梯。譬如说对于战力分别为 6, 5, 1, 2, 3, 4, 0 的一个分布来说，第一个向前看去看到的对手人数为 0，第二个向前看去能看到战力为 6 的人，看到的对手人数为 1，第三个向前看去能看到战力为 6, 5 的 2 人，第四个向前看去能看到战力为 6, 5 的 2 人，第五个向前看去能看到战力为 6, 5 的 2 人，第六个向前看去能看到战力为 6, 5 的 2 人，第七个向前看去能看到战力为 4, 5, 6 的 3 人。而战力为 1, 2, 3 的人会被战力为 4 的人所屏蔽掉。 Input
输入数据有多组（数据组数不超过 20），到 EOF 结束。 对于每组数据： 第一行输入一个整数 n, m 表示要统计的总人数和询问的次数。 接下来一行有 n 个以空格分隔的正整数，表示 n 个人的战力分布。 接下来 m 行，每行一个正整数 pos，表示要询问的人的位置，位置标号按照输入从 1~n。 数据范围：1 <= n, m <= 100000，战力范围为 1~1000。 Output
对于每组数据中的每次询问，输出一个正整数表示此人向前看去能够看到的对手（威胁）数。 Example Input
7 7 6 5 1 2 3 4 0 1 2 3 4 5 6 7 Example Output
0 1 2 2 2 2 3
#include<bits/stdc++.h> using namespace std; struct node { int cnt; } a[1008611]; int main() { int n, hi, i; int m; while(cin >> n >> m) { stack<int>s; // scanf("%d",&hi); // s.push(hi); for (i = 1; i <= n; i ++) { a[i].cnt = 0; scanf("%d",&hi); while(!s.empty() && s.top() <= hi) s.pop(); a[i].cnt = a[i].cnt + s.size(); s.push(hi); } for (i = 1; i <= m; i ++) { int key; cin >> key; cout << a[key].cnt << endl; } } }