[NPSC] 2009初賽 E. 檸檬汽水傳說

題目連結:http://contest.cc.ntu.edu.tw/npsc2009/2009sen.pdf

---

不 本題複雜度大概要做到$O(n)$或$O(n \log n)$，所以明顯naive的枚舉點對做法是不可能會好的，不妨思考其實每個人都只要往一邊看就好了，而且當看到一個比自己大的數就可以停了，那應該可用stack做，而明顯要用stack做的話，要有一定的單調性，想想後發現遞減的是好的，每次都pop掉比自己小的人並把pop了幾個加上去，不過值得注意的是如果是pop掉跟自己一樣的人的話，記得要把他原本的size記錄下來，之後要擺回去，因為其他人都還是可以跟你做匹配之類的，此外因為每個人都還可以跟隔壁的人溝通，所以當隔壁有人時記得多加一。

#include <bits/stdc++.h>
using namespace std;

class knight{
	private:
		int __val;
		long long __size;
	public:
		knight(int a,int b){__val=a;__size=b;}
		int operator++(int a){if(a==0)return __size++;}
		bool operator<=(int a){return __val<=a;}
		bool operator==(int a){return __val==a;}
		friend void operator+=(long long &a, knight b){a+=b.__size;}
};

stack<knight> ss;

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int sz;
		long long ans=0;
		scanf("%d",&sz);
		while(!ss.empty())ss.pop();
		for(int i=0;i<sz;i++){
			int aaa;
			scanf("%d",&aaa);
			long long kk=1;
			while(!ss.empty()&&(ss.top()<=aaa)){
				if(ss.top()==aaa) kk+=ss.top();
				ans+=ss.top();
				ss.pop();
			}
			if(!ss.empty())ans++;
			ss.push(knight(aaa,kk));
		}
		printf("%lld\n",ans);
	}
	return 0;
}