HDU5141--LIS again （LIS变形）

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = 1e5+;
int seg[maxn<<],pt[maxn<<],a[maxn],vec[maxn],idx,n;
int pos1[maxn],pos2[maxn];
void hash_()
{
sort(vec,vec+idx);
idx = unique(vec,vec+idx) - vec;
for (int i = ; i < n ;i++)
a[i] = lower_bound(vec,vec+idx,a[i]) - vec + ;
}
int ans,pp;
/*
void update(int l,int r,int pos,int x,int val,int s)
{
if (l == r)
{
if (val == seg[pos] && s > pt[pos])
pt[pos] = s;
if (val > seg[pos])
{
pt[pos] = s;
seg[pos] = val;
}
return ;
}
int mid = (l + r) >> 1;
if (x <= mid)
update(l,mid,pos<<1,x,val,s);
else
update(mid+1,r,pos<<1|1,x,val,s);
seg[pos] = max(seg[pos<<1],seg[pos<<1|1]);
if (seg[pos<<1] > seg[pos<<1|1])
pt[pos] =pt[pos<<1];
if (seg[pos<<1] < seg[pos<<1|1])
pt[pos] = pt[pos<<1|1];
if (seg[pos<<1] == seg[pos<<1|1])
pt[pos] = max(pt[pos<<1],pt[pos<<1|1]);
}
void query(int l,int r,int pos,int ua,int ub)
{
if (ub < ua)
return ;
if (ua <= l && ub >= r)
{
if (ans < seg[pos])
{
ans = seg[pos];
pp = pt[pos];
}
if (ans == seg[pos] && pp < pt[pos])
pp = pt[pos];
return ;
}
int mid = (l + r) >> 1;
if (ua <= mid)
query(l,mid,pos<<1,ua,ub);
if (ub > mid)
query(mid+1,r,pos<<1|1,ua,ub);
}*/
inline int lowbit (int x)
{
return x & -x;
}
int c[][maxn];
void add(int x,int d,int s)
{
while (x <= idx)
{
if (c[][x] < d)
{
c[][x] = d;
c[][x] = s;
}
if (c[][x] == d && c[][x] < s)
{
c[][x] = s;
}
x += lowbit(x);
}
}
void query(int x)
{
while (x)
{
if (ans < c[][x])
{
pp = c[][x];
ans = c[][x];
}
if (ans == c[][x] && pp < c[][x])
{
pp = c[][x];
}
x -= lowbit(x);
}
}
int dp[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while (~scanf ("%d",&n))
{
//memset(seg,0,sizeof(seg));
//memset(pt,0,sizeof(pt));
memset(c,,sizeof(c));
idx = ;
for (int i = ; i < n; i++)
{
scanf("%d",a+i);
vec[idx++] = a[i];
}
hash_();
int LIS = ;
for (int i = ; i < n; i++)
{
ans = ;
//query(1,n,1,1,a[i]-1);
query(a[i]-);
dp[i] = ans + ;
if (ans == )
pos1[i] = i;
else
pos1[i] = pp;
// update(1,n,1,a[i],dp[i],pos1[i]);
add(a[i],dp[i],pos1[i]);
LIS = max(dp[i],LIS);
}
int pre = n;
for (int i = n -; i >= ; i--)
{
if (dp[i] != LIS)
continue;
pos2[i] = pre-;
pre = i;
}
ll cnt = ;
for (int i = ; i < n; i++)
{
if (dp[i] != LIS)
continue;
cnt += (ll)(pos1[i] + ) * (pos2[i]+-i);
}
printf("%I64d\n",cnt);
}
return ;
}