记录编号	245548	评测结果	AAAAAAAAAA
题目名称	学数数	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.804 s
提交时间	2016-04-03 17:47:31	内存使用	7.73 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
const int maxn = 1e5+10;
typedef long long LL;
inline int get_num(int &ans) {
	ans = 0;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp <= '9' && tmp >= '0') {
		ans = ans*10 + tmp - '0';
		tmp = getchar();
	}
}
inline int get_num(int &ans, char &han) {
	ans = 0;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') {
		if(tmp == '=' || tmp == '<' || tmp == '>') han = tmp;
		tmp = getchar();
	}
	while(tmp <= '9' && tmp >= '0') {
		ans = ans*10 + tmp - '0';
		tmp = getchar();
	}
}
int v[maxn];//值 
int rank[maxn];//值的有序序列 
int tar[maxn];//值的位置 
int l[maxn];//左覆盖区间 
int r[maxn]; //右覆盖区间 
int n, q, cnt;
LL cover[maxn];//覆盖范围 
LL psum[maxn], ssum[maxn];//前缀和，后缀和 
 
 
template <class T> class stack {
private:
	T a[maxn];
	int top_;
public:
	inline stack() { top_ = 0; }
	inline void push(T tar) { a[++top_] = tar; }
	inline void pop() { --top_; }
	inline T top() { return a[top_]; }
	inline bool nempty() { return top_; }
	inline void clear() { top_ = 0; }
}; 
 
 
inline void read() {
	get_num(n); get_num(q);
	for(int i = 1; i <= n; ++i) {
		get_num(v[i]);
	}
	memcpy(tar, v, (n+1) << 2);
}
 
stack<int> s; 
 
inline void handle() {
	sort(v+1, v+n+1);//排序 
	for(int i = 1; i <= n; ++i) {//去重(为了方便离散化处理)
		if(v[i] == v[i-1]) continue;
		rank[++cnt] = v[i];
	}
	for(int i = 1; i <= n; ++i) {
		tar[i] = lower_bound(rank+1, rank+cnt+1, tar[i]) - rank;//排序后的rank值 
	}
	for(int i = 1; i <= n; ++i) {//处理从当前位置起向右最多能覆盖到哪一位 
		while(s.nempty() & tar[i] > tar[s.top()]) { r[s.top()] = i-1; s.pop(); }//如果当前的数大于栈顶，那说明栈顶最多覆盖到当前数的前一位 
		s.push(i);
	}
	while(s.nempty()) { r[s.top()] = n; s.pop(); }//栈里剩下的元素都是能覆盖的n的 
	for(int i = n; i >= 1; --i) {//处理从当前位置起向左最多能覆盖到哪一位 
		while(s.nempty() & tar[i] >= tar[s.top()]) { l[s.top()] = i+1; s.pop(); }//如果当前的数大于栈顶，那说明栈顶最多覆盖到当前数的后一位 
		s.push(i);
	}
	while(s.nempty()) { l[s.top()] = 1; s.pop(); }//栈里剩下的元素都是能覆盖的1的 
	for(int i = 1; i <= n; i++) {//确定覆盖区间 
		cover[tar[i]] += (LL)(i-l[i]+1) * (LL)(r[i]-i+1);//如果有重复，这里会一起加上
	} 
	for(int i = 1; i <= cnt; i++) {
		psum[i] = psum[i-1]+cover[i];
		ssum[cnt-i+1] = ssum[cnt-i+2] + cover[cnt-i+1];
	}
}
 
inline void sovle() {
	char han;
	int num;
	int pos;
	for(int i = 1; i <= q; ++i) {
		get_num(num, han);
		if(han == '=') {//直接找到对应cover中的位置输出即可 
			pos = lower_bound(rank+1, rank+cnt+1, num) - rank; //找到要查询元素的位置
			if(rank[pos] != num) printf("0\n");//如果该元素在数组中并不存在 
			else printf("%lld\n", cover[pos]);
		} else if(han == '<') {//需要要查询该数位置之前的所有的数(前缀和)，这里去重的优势就体现出来啦~ 
			pos = lower_bound(rank+1, rank+cnt+1, num) - rank;//大于等于num
			printf("%lld\n", psum[pos-1]);//所以减一 
		} else {//需要要查询该数位置之后的所有的数(后缀和)
			pos = upper_bound(rank+1, rank+cnt+1, num) - rank;//大于num 
			printf("%lld\n", ssum[pos]);//已经满足 
		}
	}
}
int main() {
	freopen("jxthree.in", "r", stdin);
	freopen("jxthree.out", "w", stdout);
	read();
	handle();
	sovle();
	return 0;
}