我终于知道花儿为什么那么红
by 日月影 @ 2017-10-12 10:20:07
来个人tell me为什么错啊。。。
我的：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010;
int w[N],a[N],f[N][20],r[N],l[N];
int Log[N],tot;
int limit;
int n,m,x,y;
long long ans[N],fl[N],fr[N],now;
struct data
{
int l,r;
int id;
friend bool operator <(const data &a,const data &b){
if(a.l/limit==b.l/limit) return a.r<b.r;
return a.l/limit<b.l/limit;
}
}q[N];
int query(int l,int r)
{
int pos=Log[r-l+1];
if(a[f[l][pos]]<a[f[r-(1<<pos)+1][pos]]) return f[l][pos];
return f[r-(1<<pos)+1][pos];
}
void preper()
{
for(int i=1;i<=n;i++)
{
Log[i]=(int)log2(i);
}
for(int i=1;i<=n;i++)
{
while(tot>0&&a[w[tot]]>a[i]) r[w[tot--]]=i;
l[i]=a[w[tot]]==a[i]?l[w[tot]]:w[tot];
w[++tot]=i;
}
while(tot) r[w[tot--]]=n+1;
for(int i=1;i<=n;i++) fl[i]=fl[l[i]]+1ll*(i-l[i])*a[i];
for(int i=n;i>=1;i--) fr[i]=fr[r[i]]+1ll*(r[i]-i)*a[i];
for(int i=1;i<=n;i++) f[i][0]=i;
for(int i=1;(1<<i)<=n;i++)
{
for(int j=1;j<=n-(1<<i)+1;j++)
{
if(a[f[j][i-1]]<a[f[j+(1<<(i-1))][i-1]]) f[j][i]=f[j][i-1];
else f[j][i]=f[j+(1<<(i-1))][i-1];
}
}
}
void calcl(int l,int r,long long k)
{
int pos=query(l,r);
now+=k*(a[pos]*(r-pos+1)+fr[l]-fr[pos]);
}
void calcr(int l,int r,long long k)
{
int pos=query(l,r);
now+=k*(a[pos]*(pos-l+1)+fl[r]-fl[pos]);
}
void read(int &x)
{
static char c;
int f=1;
for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(x=0;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
x=x*f;
}
int main()
{
read(n);read(m);
limit=(int) sqrt(n);
for(int i=1;i<=n;i++)
{
read(a[i]);
}
preper();
for(int i=1;i<=m;i++)
{
read(q[i].l);read(q[i].r);
q[i].id=i;
}
sort(q+1,q+m+1);
x=y=1;
now=a[1];
for(int i=1;i<=m;i++)
{
if(q[i].r>y) while(q[i].r>y) y++,calcr(x,y,1);
if(q[i].l>x) while(q[i].l>x) calcl(x,y,-1),x++;
if(q[i].l<x) while(q[i].l<x) x--,calcl(x,y,1);
if(q[i].r<y) while(q[i].r<y) calcr(x,y,-1),y--;
ans[q[i].id]=now;
}
for(int i=1;i<=m;i++)
{
printf("%lld\n",ans[i]);
}
return 0;
}
```
别人的：
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
const int N=100010;
int stk[N],a[N],rmq[N][20],r[N],l[N],Log[N],top,S,n,m,x,y;
long long ans[N],dl[N],dr[N],now;
struct query{
int l,r,id;
friend bool operator <(const query &a,const query &b){
if(a.l/S==b.l/S) return a.r<b.r;
return a.l/S<b.l/S;
}
}q[N];
inline void Read(int &x){
static char c;
int f=1;
for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(x=0;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
x=x*f;
}
int query(int l,int r){
int tmp=Log[r-l+1];
if(a[rmq[l][tmp]]<a[rmq[r-(1<<tmp)+1][tmp]])
return rmq[l][tmp];
else return rmq[r-(1<<tmp)+1][tmp];
}
void changel(int l,int r,long long k){
int tmp=query(l,r);cout<<tmp<<' ';
now+=k*a[tmp]*(r-tmp+1);
now+=k*(dr[l]-dr[tmp]);
}
void changer(int l,int r,long long k){
int tmp=query(l,r);cout<<tmp<<' ';
now+=k*a[tmp]*(tmp-l+1);
now+=k*(dl[r]-dl[tmp]);
}
void pretreat(){
for(int i=1;i<=n;i++) Log[i]=(int)log2(i);
for(int i=1;i<=n;i++){
while(top&&a[stk[top]]>a[i]) r[stk[top--]]=i;
l[i]=a[stk[top]]==a[i]?l[stk[top]]:stk[top];
stk[++top]=i;
}
while(top) r[stk[top--]]=n+1;
for(int i=1;i<=n;i++) dl[i]=dl[l[i]]+1ll*(i-l[i])*a[i];
for(int i=n;i;i--) dr[i]=dr[r[i]]+1ll*(r[i]-i)*a[i];
for(int i=1;i<=n;i++) rmq[i][0]=i;
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j<=n-(1<<i)+1;j++){
if(a[rmq[j][i-1]]<a[rmq[j+(1<<(i-1))][i-1]])
rmq[j][i]=rmq[j][i-1];
else rmq[j][i]=rmq[j+(1<<(i-1))][i-1];}
}
int main(){
Read(n); Read(m);
S=(int)sqrt(n);
for(int i=1;i<=n;i++) Read(a[i]);
pretreat();
for(int i=1;i<=m;i++){
Read(q[i].l); Read(q[i].r);
q[i].id=i;
}
sort(q+1,q+1+m);
x=y=1; now=a[1];
for(int i=1;i<=m;i++){
if(q[i].r>y) while(y!=q[i].r) y++,changer(x,y,1);
if(q[i].l>x) while(x!=q[i].l) changel(x,y,-1),x++;
if(q[i].l<x) while(x!=q[i].l) x--,changel(x,y,1);
if(q[i].r<y) while(y!=q[i].r) changer(x,y,-1),y--;
ans[q[i].id]=now;
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}
```
明明一模一样
by 日月影 @ 2017-10-12 10:22:02