站外题求助
快速排序
题目描述
Maxtir有一个长度为2n的序列{Ci}，为了美观，他使这个序列有序。Maxtir想要将它分离，即把它分成两个长度为的子序列{ai}，{bi}，方法如下：
- 构造两个长度为的整数序列{si}，{ti}，使得：当1<=i<=n时，si<ti；
- 当1<=i<=n时，令ai=Csi，令bi=Cti。 Maxtir定义分离后的两个子序列的差距为∑（bi-ai）。他想考一下Sao，问对于区间[l,r]的所有分离方式，两个子序列的差距最大值和最小值分别是多少。同时，他想顺便知道一下，分离区间[l,r]一共有多少种不同方案。两种方案不同，当且仅当存在不同。 Sao觉得这个问题不够好玩。他想要修改序列，每次修改会使序列一段区间加上一个相同的数。但是Sao诚实地告诉了Maxtir，他不会破坏序列有序的性质。Maxtir不擅长计算，所以把问题交给了你。由于最终答案较大，答案模10^9+7。
输入格式
第1行输入两个正整数n,m，m表示修改和询问的总数。 第2行输入2n个非负整数表示。 第3至m+2行，每行输入三至四个整数： 0 l r val表示Sao将区间[l,r]加上val。 1 l r表示Maxtir求区间[l,r]分离后的最大差距、最小差距和方案数。
输出格式
对于每个询问，输出一行三个整数，分别表示最大差距、最小差距和方案数。
样例 #1
样例输入 #1
3 3
1 2 3 4 5 6
1 1 6
0 1 6 10
1 1 6
样例输出 #1
9 3 5
9 3 5
样例 #2
样例输入 #2
5 5
1 2 3 4 5 6 7 8 9 10
1 1 10
0 7 10 10
1 1 10
0 3 6 5
1 1 10
样例输出 #2
25 5 42
65 5 42
55 5 42
提示
对于20%的数据，n,m<=10,Ci<=10^3。 对于20%的数据，n,m<=310^3,Ci<=10^4。 对于100%的数据，n,m<=510^5,Ci<=10^5，-10^5<=val<=10^5，1<=l<=r<=2n且区间长度为偶数。
我的代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
ll f[500005],n,m,c[1000005],b[1000005];
struct tree
{
ll l,r;
ll s1/*偶数位和*/,s/*和*/,tag;
}e[4000005];
void build(ll p,ll l,ll r)
{
e[p].l=l;
e[p].r=r;
e[p].tag=0;
if(l==r)
{
e[p].s1=0;
e[p].s=c[l];
return;
}
ll mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
if((mid-l+1)%2==1)
e[p].s1=e[p*2].s1+(e[p*2+1].s-e[p*2+1].s1);
else
e[p].s1=e[p*2].s1+e[p*2+1].s1;
e[p].s=e[p*2].s+e[p*2+1].s;
}
void down(ll p)
{
if(e[p].tag==0)
return;
e[p*2].tag+=e[p].tag;
e[p*2+1].tag+=e[p].tag;
e[p*2].s+=(e[p*2].r-e[p*2].l+1)*e[p].tag;
e[p*2].s1+=(e[p*2].r-e[p*2].l+1)/2*e[p].tag;
e[p*2+1].s+=(e[p*2+1].r-e[p*2+1].l+1)*e[p].tag;
e[p*2+1].s1+=(e[p*2+1].r-e[p*2+1].l+1)/2*e[p].tag;
e[p].tag=0;
}
void add(ll p,ll l,ll r,ll x)
{
if(l<=e[p].l&&r>=e[p].r)
{
e[p].tag+=x;
e[p].s+=(e[p].r-e[p].l+1)*e[p].tag;
e[p].s1+=(e[p].r-e[p].l+1)/2*e[p].tag;
return;
}
int mid=(e[p].l+e[p].r)/2;
if(l<=mid)
add(p*2,l,r,x);
if(r>mid)
add(p*2+1,l,r,x);
if((mid-e[p].l+1)%2==1)
e[p].s1=e[p*2].s1+(e[p*2+1].s-e[p*2+1].s1);
else
e[p].s1=e[p*2].s1+e[p*2+1].s1;
e[p].s=e[p*2].s+e[p*2+1].s;
return ;
}
ll query2(ll l,ll r,ll p)//查询和
{
if(l>e[p].r||r<e[p].l)
return 0;
down(p);
if(e[p].r<=r&&e[p].l>=l)
return e[p].s;
return query2(l,r,p*2)+query2(l,r,p*2+1);
}
ll query1(ll l,ll r,ll p)//查询偶数项的和
{
if(l>e[p].r||r<e[p].l)
return 0;
if(e[p].r<=r&&e[p].l>=l)
return e[p].s1;
down(p);
int mid=(e[p].l+e[p].r)/2;
int ss=0;
bool f=0;
if(l<=mid)
{
ss=query1(l,r,p*2);
if((mid-l+1)%2==1)
f=1;
}
if(r>mid)
{
int t=query1(l,r,p*2+1);
if(f)
ss+=(query2(l,r,p*2+1)-t);
else
ss+=t;
}
return ss;
}
ll qp(ll a,ll b)
{
int s=1;
while(b)
{
if(b&1)
s=s*a%mod;
a=a*a%mod;
b/=2;
}
return s%mod;
}
void init()
{
f[0]=f[1]=1;
for(ll i=2;i<=n*2;i++)
f[i]=(f[i-1]%mod*(4*i-2)%mod*qp(i+1,1ll*mod-2)%mod+mod)%mod;
}
int main()
{
scanf("%lld%lld",&n,&m);
init();
for(int i=1;i<=2*n;i++)
scanf("%lld",&c[i]);
init();
build(1,1,2*n);
for(int i=1;i<=m;i++)
{
int t,l,r;
scanf("%d%d%d",&t,&l,&r);
if(t==0)
{
ll val;
scanf("%lld",&val);
add(1,l,r,val);
}
else
{
ll s1=0,s2=0,s=query2(l,r,1);
printf("%lld %lld %lld\n",query2((l+r+1)/2,r,1)*2-s,query1(l,r,1)*2-s,f[(r-l+1)/2]%mod);
}
}
return 0;
}
这是一个数据：
输入
10 10
22 24 38 41 49 51 61 63 65 66 67 68 69 72 80 80 83 85 87 96
1 6 9
0 3 14 6
1 4 13
0 15 20 0
1 3 6
0 3 4 -10
1 6 9
1 4 7
0 2 11 -2
0 1 6 -4
正确答案：
16 12 2
70 22 42
21 5 2
16 12 2
32 28 2
我的输出：
16 12 2
70 22 42
21 5 2
16 12 2
26 12 2
有没有大佬能帮我看看是为什么（）
应该是线段树查询部分的问题，但是我调不出来……
加载中...