单调栈

2019/04/19 20:47

$1$进栈，栈内无元素，$L_1=0$ $(1)$

$5​$进栈，无出栈，$L_2=1​$（栈顶元素） $(1,5)​$

$2$进栈，$5$出栈，$R_2$（出栈元素）$=3$（当前元素），$L_3=1$ $(1,2)$

$6$进栈，无出栈，$L_4=3$ $(1,2,6)$

$4​$进栈，$6​$出栈，$R_4=5​$，$L_5=3​$ $(1, 2, 4)​$

$3​$进栈，$4​$出栈，$R_5=6​$，$L_6=5​$ $(1,2,3)​$

int main()
{
//读入
stack<int> s; int l[N], r[N];
for (int i=1; i<=n; i++)
{
while ((!s.empty()) && a[s.top()]>a[i]) {r[s.top()]=i; s.pop();}
if (!s.empty()) l[i]=s.top(); else l[i]=0;
s.push(i);
}
while (!s.empty()) {r[s.top()]=n+1; s.pop();}
}


#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N], l[N], r[N];
stack<int> s;

{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}

int main()
{
int n;
while (scanf("%d",&n)!=EOF&&n)
{
for (int i=1; i<=n; i++) a[i]=read();
for (int i=1; i<=n; i++)
{
while ((!s.empty()) && a[s.top()]>a[i])
{r[s.top()]=i; s.pop();}
if (!s.empty()) l[i]=s.top();
else l[i]=0;
s.push(i);
}
while (!s.empty()) {r[s.top()]=n+1; s.pop();}
long long ans=0;
for (int i=1; i<=n; i++) ans=max(ans, 1ll*a[i]*(r[i]-l[i]-1));
printf("%lld\n",ans);
}
return 0;
}



#include<bits/stdc++.h>
using namespace std;
stack<pair<int, int> > s;

{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}

int main()
{
for (int i=1; i<=n; i++)
{
int h=read(); pair<int, int> p=make_pair(h, 1);
for (; (!s.empty()) && s.top().first<=h; s.pop())
{
ans+=s.top().second;
if (s.top().first==h) p.second+=s.top().second;
}
if (!s.empty()) ans++;
s.push(p);
}
printf("%lld\n",ans);
return 0;
}


#include<cstdio>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=1005, P=1000000007;
inline int max(int a, int b){return a>b?a:b;}
int a[N][N], h[N], s[N], cnt[N], n, top, And, Or;

{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}

int calc(int n){return 1ll*n*(n+1)>>1;}

int solve(int x)
{
int res=0;
rep(i, 1, n) h[i]=0;
rep(i, 1, n)
{
rep(j, 1, n)
{
if ((a[i][j]&1)==x) h[j]++; else h[j]=0;
if (h[j]>s[top]) s[++top]=h[j], cnt[top]=1;
else
{
int tmp=0;
while (s[top]>h[j])
{
tmp+=cnt[top];
res=(res+1ll*(s[top]-max(h[j], s[top-1]))*calc(tmp)%P)%P;
--top;
}
s[++top]=h[j]; cnt[top]=tmp+1;
}
}
int tmp=0;
while (top)
{
tmp+=cnt[top];
res=(res+1ll*calc(tmp)*(s[top]-s[top-1])%P)%P;
--top;
}
}
return res;
}

int main()
{
rep(i, 1, n) rep(j, 1, n) a[i][j]=read();
rep(i, 0, 31)
{
And=(And+1ll*solve(1)*(1<<i)%P)%P;
Or=(Or+1ll*(1ll*calc(n)*calc(n)%P-solve(0))*(1<<i))%P;
rep(j, 1, n) rep(k, 1, n) a[j][k]>>=1;
}
printf("%d %d\n", And, (Or+P)%P);
return 0;
}


#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=100005;
struct node{int sum, cnt;}s1[N], s2[N];
bool operator < (node a, node b){return a.sum*b.cnt<b.sum*a.cnt;}
node operator + (node a, node b){return (node){a.sum+b.sum, a.cnt+b.cnt};}
int a[N], b[N], c[N<<1], cnt1, cnt2, tot, ans;

{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}

signed main()
{
rep(i, 1, n)
{
s1[++cnt1]=(node){a[i], 1};
while (cnt1 && s1[cnt1-1]<s1[cnt1])
s1[cnt1-1]=s1[cnt1-1]+s1[cnt1], cnt1--;
}
rep(i, 1, m)
{
s2[++cnt2]=(node){b[i], 1};
while (cnt2 && s2[cnt2-1]<s2[cnt2])
s2[cnt2-1]=s2[cnt2-1]+s2[cnt2], cnt2--;
}
int l1=1, l2=1, L1=1, L2=1;
s1[cnt1+1].sum=s2[cnt2+1].sum=-1;
s1[cnt1+1].cnt=s2[cnt2+1].cnt=1;
while (l1<=cnt1 || l2<=cnt2)
if (s2[l2]<s1[l1])
{
rep(i, L1, L1+s1[l1].cnt-1) c[++tot]=a[i];
L1+=s1[l1++].cnt;
}
else
{
rep(i, L2, L2+s2[l2].cnt-1) c[++tot]=b[i];
L2+=s2[l2++].cnt;
}
rep(i, 1, n+m) ans+=i*c[i]; printf("%lld\n", ans);
return 0;
}


0
0 收藏

0 评论
0 收藏
0