洛谷 P10798 「CZOI-R1」消除威胁

题目来源于：洛谷

题目本质：贪心，st表，单调栈

解题思路：由于昨天联练习了平衡树，我就用平衡树+STL打了个暴力，超时得了30分

这是暴力代码：

#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> h;
unordered_map<int,int> last;
const int N=5e5+10; 
struct edge{int l,r;int val;
}tr[N*4];
int n;
int a[N];
struct tree{int p;int next;
}e[N];
int ll(int x){return x<<1;
}
int rr(int x){return x<<1|1;
}
void build(int p,int l,int r){tr[p].l=l;tr[p].r=r;if(l==r){tr[p].val=abs(a[l]);return ;}int mid=l+r>>1;build(ll(p),l,mid);build(rr(p),mid+1,r);tr[p].val=max(tr[ll(p)].val,tr[rr(p)].val);
}
int ask(int p,int x,int y){if(x<=tr[p].l&&y>=tr[p].r){return tr[p].val;}int ans=-1e18;int mid=tr[p].l+tr[p].r>>1;if(x<=mid) ans=max(ask(ll(p),x,y),ans);if(y>mid) ans=max(ask(rr(p),x,y),ans);return ans;
}
signed main(){scanf("%d",&n);bool jude=true;int r=1e9+1;for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(r==1e9+1) r=abs(a[i]);else if(r!=abs(a[i])) jude=false;if(last[abs(a[i])]==0){if(a[i]>0) a[i]=-a[i];last[abs(a[i])]=1;}else{if(a[i]<0) a[i]=-a[i];last[abs(a[i])]=0;}e[i].p=i;e[i].next=h[a[i]];h[a[i]]=i;}if(jude){long long x=n/2;long long y=(n+1)/2;printf("%lld",x*(x-1)/2+y*(y-1)/2);return 0;}build(1,1,n);int sum=0; for(int i=1;i<=n;i++){for(int j=h[a[i]];j!=0;j=e[j].next){if(e[j].p<=i) break;;if(ask(1,i,e[j].p)==abs(a[i])) sum++;}}printf("%lld",sum);return 0;
} 

后来看了洛谷题解才晓得原来用比这个代码短多了的方法就能实现，注意到可以进行任意次取反操作，而对同一个数做两次取反相当于没做，所以问题可以转化成每一个数取不取反。直接使用绝对值就好了。如果当前元素小于栈顶元素，就直接插进去。如果当前元素大于栈顶元素，破坏了单调栈的单调性，就一直弹栈顶元素，弹到栈顶元素小于等于当前元素。如果栈顶元素等于当前元素，那么以栈顶元素为开始的连续威胁区间个数cnt(stop​)）加 1。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n;
int a[500005], cnt[500005];
stack<int> s;
int f[500005];
int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];a[i] = abs(a[i]);}for (int i = 1; i <= n; i++) {while (!s.empty() && a[s.top()] < a[i])s.pop();if (!s.empty() && a[s.top()] == a[i])cnt[s.top()]++;elses.push(i);}long long ans = 0;for (int i = 1; i <= n; i++) {int N = cnt[i] + 1, M = N / 2;if (!a[i])ans += 1ll * N * (N - 1) / 2;elseans += 1ll * M * (M - 1) / 2 + 1ll * (N - M) * (N - M - 1) / 2;}cout << ans;return 0;
}