杭州集训第五天

#include
using namespace std;
long long n;
long long ans;
long long a[1000005];
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=1;i)
{
int x=a[i],y=a[i+1];
if(x>y)
{
ans=(long long)ans+(x-y)*(n-x+1);
}
else
{
ans=ans+(long long)(y-x)*x;
}
}
ans+=(long long)a[n]*(n-a[n]+1);
cout<<ans;
return 0;
}

#include
using namespace std;
int n,t;
struct tree{
int l,r;
long long dat;
}e[4000000];
map<int,int>q;
long long a[1000000];
long long b[1000000];
long long ans;
long long sum;
long long c[1000000];
int cnt;
int Read()
{
char w=getchar();
int ch=0;
while(w<‘0‘||w>‘9‘){
w=getchar();
}
while(w>=‘0‘&&w<=‘9‘){
ch=ch*10+w-‘0‘;
w=getchar();
}
return ch;
}
void build(int q,int l,int r)
{
e[q].l=l;
e[q].r=r;
e[q].dat=0;
if(l==r)
return;
int mid=(l+r)>>1;
build(q*2,l,mid);
build(q*2+1,mid+1,r);
}
void add(int q,int l,long long val)
{
if(e[q].l==e[q].r&&e[q].r==l)
{
e[q].dat=max(e[q].dat,val);
return;
}
int mid=(e[q].l+e[q].r)>>1;
if(mid>=l) add(q*2,l,val);
if(mid2+1,l,val);
e[q].dat=max(e[q*2].dat,e[q*2+1].dat);
}
long long ask(int q,int l,int r)
{
long long num=0;
if(e[q].l>=l&&e[q].r<=r)
return e[q].dat;
int mid=(e[q].l+e[q].r)>>1;
if(mid>=l) num=max(num,ask(q*2,l,r));
if(mid2+1,l,r));
return num;
}
int main()
{
t=Read();
while(t--){
n=Read();
ans=0; sum=0;
for(int i=1;i<=n;i++)
{
a[i]=Read();
b[i]=a[i];
sum+=a[i];
}
build(1,1,n);
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
if(i==1||b[i]!=b[i-1])
q[b[i]]=++cnt;
else
q[b[i]]=cnt;
}
for(int i=1;i<=n;i++)
c[i]=q[a[i]];
for(int i=1;i<=n;i++)
{
long long f=ask(1,1,c[i])+a[i];
add(1,c[i],f); ans=max(f,ans);
}
for(int i=1;i<=n;i++)
q[a[i]]=0;
cnt=0;
cout<endl;
}
return 0;
}