当前位置: 首页 > news >正文

中山快速做网站价格百度贴吧网页版

中山快速做网站价格,百度贴吧网页版,合肥个人做网站,如何增加网站收录题目来源于&#xff1a;洛谷 题目本质&#xff1a;贪心&#xff0c;st表&#xff0c;单调栈 解题思路&#xff1a;由于昨天联练习了平衡树&#xff0c;我就用平衡树STL打了个暴力&#xff0c;超时得了30分 这是暴力代码&#xff1a; #include<bits/stdc.h> using name…

题目来源于:洛谷

题目本质:贪心,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;
}

http://www.hrbkazy.com/news/21983.html

相关文章:

  • 网站定制的销售情况优化网站排名如何
  • 淘宝建设网站靠谱吗互联网营销师怎么做
  • 有什么网站是做企业型的夫唯seo视频教程
  • 认证网站源码电脑优化大师官方免费下载
  • 广东汽车品牌网站建设seo根据什么具体优化
  • seo静态页源码百度seo优化方法
  • 高密做网站哪家好一般网络推广应该怎么做
  • 太原seo快速排名百度推广seo怎么学
  • 网站开发就业趋势百度网盘资源
  • 重庆做网站优化网络宣传平台有哪些
  • 类似火脉的推广平台深圳抖音seo
  • 武汉平价网站建设百度爱采购优化软件
  • 网站开发完后期维护重要吗seo怎么发外链的
  • 有域名之后怎么做网站广州seo关键字推广
  • o2o商超网站建设松松软文
  • 做网站用什么免费字体百度推广竞价排名技巧
  • 黑龙江省网站建设哈尔滨最新疫情
  • 尚品中国多年专注于高端网站建设软文广告案例
  • 企业名网站自然优化
  • 常熟专业做网站东莞网络推广营销
  • 忻州做网站app开发费用一般多少钱
  • 化妆品公司网站建设方案推广赚钱的软件排行
  • 游戏公司网站模板培训如何优化网站
  • 荣耀手机商城官方网站售后seo排名优化服务
  • 合肥 网站制作seo网站关键词排名优化
  • 网站建设 服饰鞋帽搜狗链接提交入口
  • p2p网站怎么做网络营销案例分析ppt
  • 中国建设银行注册网站代运营公司
  • phpcms网站转移win7优化大师下载
  • 网站建设背景域名seo站长工具