【数据结构2-2】线段树与树状数组 题解
头一次老老实实写完一个官方题单，发篇题解纪念一下。
@[TOC]
P3372 【模板】线段树 1
令人惆怅，第一个模板题就有延迟标记。
1 |
|
P3373 【模板】线段树 2
令人叹惋，第二个模板题就这么难调。
区间乘法：将整个区间上的数乘上一个数时同时要把它储存的add和mud都乘上该数。每次延迟标记下放遵循“先乘后加”：先把区间上的数乘上储存的mu再作区间加法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using namespace std;
int n,m,a[1000005],mod;
struct segment_tree
{
ll sum,l,r,mu,add;
}t[1000005];
ll read()
{
ll x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
void build(ll p,ll l,ll r)
{
t[p].l=l,t[p].r=r,t[p].mu=1;//乘法运算的幺元是1
if(l==r)
{
t[p].sum=a[l]%mod;
return;
}
ll mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void spread(ll p)//重点关注 ！！！
{
t[p*2].sum=(t[p*2].sum*t[p].mu+(t[p*2].r-t[p*2].l+1)*t[p].add%mod)%mod;
t[p*2+1].sum=(t[p*2+1].sum*t[p].mu+(t[p*2+1].r-t[p*2+1].l+1)*t[p].add%mod)%mod;
t[p*2].mu=(t[p*2].mu*t[p].mu)%mod;
t[p*2+1].mu=(t[p*2+1].mu*t[p].mu)%mod;
t[p*2].add=(t[p*2].add*t[p].mu+t[p].add)%mod;
t[p*2+1].add=(t[p*2+1].add*t[p].mu+t[p].add)%mod;
t[p].add=0;
t[p].mu=1;
}
void pluss(ll p,ll l,ll r,ll x)
{
if(l<=t[p].l&&t[p].r<=r)
{
t[p].sum=(t[p].sum+(t[p].r-t[p].l+1)*x%mod)%mod;
t[p].add+=x;
return;
}
spread(p);
ll mid=(t[p].l+t[p].r)>>1;
if(l<=mid) pluss(p*2,l,r,x);//一直都是（l,r)，算出mid仅用于比较
if(mid<r) pluss(p*2+1,l,r,x);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void mu(ll p,ll l,ll r,ll x)
{
if(l<=t[p].l&&t[p].r<=r)
{
t[p].add=(t[p].add*x)%mod;
t[p].mu=(t[p].mu*x)%mod;
t[p].sum=(t[p].sum*x)%mod;
return;
}
spread(p);
ll mid=(t[p].l+t[p].r)>>1;
if(l<=mid) mu(p*2,l,r,x);
if(mid<r) mu(p*2+1,l,r,x);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
ll ask(ll p,ll l,ll r)
{
if(l<=t[p].l&&t[p].r<=r)
return t[p].sum;
spread(p);//每次询问到这里也要下放标记
ll mid=(t[p].l+t[p].r)>>1;
ll val=0;
if(l<=mid) val=(val+ask(p*2,l,r))%mod;
if(mid<r )val=(val+ask(p*2+1,l,r))%mod;
return val;
}
int main()
{
cin>>n>>m>>mod;
for(int i=1;i<=n;i++)
a[i]=read();
build(1,1,n);
for(int i=1;i<=m;i++)
{
int op=read();
if(op==1)
{
ll cn=read(),cm=read(),cw=read();
mu(1,cn,cm,cw);
}else if(op==2)
{
ll cn=read(),cm=read(),cw=read();
pluss(1,cn,cm,cw);
}
else
{
ll cn=read(),cm=read();
cout<<ask(1,cn,cm)<<endl;
}
}
}
1 |
|
P4588 [TJOI2018]数学计算
难在看出是用线段树（没区间没修改没线段……）
题目有两个操作，一个是乘一个值，另一个是除之前乘的某个值。转化一下，操作的目的为：改变一个值，查找之前的值。
可以将数据按时间排序，在时间轴上建线段树，维护区间乘。这样的话根节点就是到现在为止的所有数的乘积。
操作1：在对应时间点上乘上该数；
操作2：找到对应的时间点将该点值修改为1，然后pushup。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using namespace std;
const int N=1e5+10;
typedef long long llg;
struct tree
{
int l,r;
llg val;
}tr[N*4];
int T,Q,M;
void build(int p,int l,int r)
{
if(l==r) tr[p]={l,r,1};
else
{
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tr[p]={l,r,1};
}
}
void mul(int p,int l,int r,int pos,llg t)
{
if(tr[p].l==tr[p].r)
{
tr[p].val*=t;
tr[p].val%=M;
return;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(pos<=mid) mul(p<<1,l,mid,pos,t);
else mul(p<<1|1,mid+1,r,pos,t);
tr[p].val=tr[p<<1].val*tr[p<<1|1].val%M;
}
void divide(int p,int l,int r,int x)
{
if(tr[p].l==tr[p].r)
{
tr[p].val=1;
return;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(x<=mid) divide(p<<1,l,mid,x);
else divide(p<<1|1,mid+1,r,x);
tr[p].val=tr[p<<1].val*tr[p<<1|1].val%M;
}
int main()
{
cin>>T;
while(T--)
{
memset(tr,0,sizeof(tr));
cin>>Q>>M;
build(1,1,Q);
for(int i=1;i<=Q;i++)
{
int op;
llg t,ans;
scanf("%d%ld",&op,&t);
if(op==1)
{
mul(1,1,Q,i,t);
printf("%ld\n",tr[1].val);
}
else
{
divide(1,1,Q,t);
printf("%ld\n",tr[1].val);
}
}
}
return 0;
}
1 |
|
P1502 窗口的星星
典中典扫描线。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using namespace std;
typedef long long ll;
const int N = 20010;
struct node{
ll x,y1,y2;
ll dat;
}a[N*2];
struct p{
ll l,r;
ll dat,add;
}t[N*4];
ll mp[N];
bool cmp(node a,node b) //将x坐标从小到大排序
{
if(a.x==b.x) return a.dat<b.dat;
return a.x<b.x;
}
void build(int p,ll l,ll r)
{
t[p].l=l,t[p].r=r;
t[p].add=0, t[p].dat=0;
if(l==r) return;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
void spread(int p) //表示p节点已经被修改，但子节点还没有被修改
{
//修改子节点，并给子节点打延迟标记
t[p*2].dat+=t[p].add;
t[p*2+1].dat+=t[p].add;
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p].add=0; //清除p的标记
}
//线段树维护的内容是在区间1 ~ m内,区域(x, y) ~ (x + w, y + h)亮度的最大值
void change(int p, ll l, ll r, ll x)
{
if(l<= t[p].l&& r>= t[p].r)
{
t[p].add+=x;
t[p].dat+=x;
return;
}
if(t[p].add) spread(p);//延迟标记
int mid =(t[p].l+t[p].r)/2;
if(l<=mid) change(p*2,l,r,x);
if(r>mid) change(p*2+1,l,r,x);
t[p].dat=max(t[p*2].dat,t[p*2+1].dat); //更新节点
}
int main()
{
int T;
cin>>T;
while(T--)
{
ll n,w,h,x,y,c;
scanf("%ld%ld%ld",&n,&w,&h);
ll num=0;
for(int i=1;i<=n; i++)
{
scanf("%ld%ld%ld",&x,&y,&c);
//矩形边界上的星星不算，所以将矩形的上边界减1
a[++num]={x,y,y+h-1,c};
mp[num]=y;
a[++num]={x+w,y,y+h-1,-c};
mp[num]=y+h-1;
}
sort(mp+1,mp+1+num);
int m=unique(mp+1,mp+1+num)-mp-1; //离散化 + 去重
for(int i=1;i<=num;i++)
{ //预处理出所有坐标离散化之后的结果
a[i].y1=lower_bound(mp+1,mp+1+m,a[i].y1)-mp;
a[i].y2=lower_bound(mp+1,mp+1+m,a[i].y2)-mp;
}
sort(a+1,a+1+num,cmp);
build(1,1,m); //建树
ll ans=0;
for(int i=1;i<=num;i++)
{
change(1,a[i].y1,a[i].y2,a[i].dat);
ans=max(ans,t[1].dat);
}
cout<<ans<<endl;
}
return 0;
}
1 |
|
P2471 [SCOI2007] 降雨量
小细节最多的一道题，调得我失去智商。
不离散化80pts（两个点RE）。
- x>=y无解，出false
- y和x均未知，maybe
- 包括y和x的整个区间都已知，按题意判断true或false
- y和x均已知但中间有未知的，按题意判断maybe或false
- 有一个未知，判断另一个与区间的大小关系maybe或false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
using namespace std;
const int N=1e5+10;
map<int,int>mp;
struct tree
{
int l,r;
int val;//降雨量
bool known;//是否已知
}tr[N*4];
int m,n,cnt,a[N],first,now,mem[N];
void build(int p,int l,int r)
{
if(l==r)
{
if(a[l]==-1)
tr[p]={l,r,0,0};
else tr[p]={l,r,a[l],1};
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tr[p].l=l,tr[p].r=r;
tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
tr[p].known=(tr[p<<1].known&&tr[p<<1|1].known)?1:0;
}
int query(int p,int l,int r)
{
if(l<=tr[p].l&&tr[p].r<=r)
{
//cout<<"tr[p].l:"<<tr[p].l<<" tr[p].r:"<<tr[p].r<<" tr[p].val:"<<tr[p].val<<endl;
return tr[p].val;
}
int mid=(tr[p].l+tr[p].r)>>1;
int maxn=0;
if(l<=mid) maxn=max(query(p<<1,l,r),maxn);
if(r>mid) maxn=max(query(p<<1|1,l,r),maxn);
return maxn;
}
bool ask(int p,int l,int r)
{
if(l<=tr[p].l&&tr[p].r<=r)
return tr[p].known;
int mid=(tr[p].l+tr[p].r)>>1;
bool flag=1;
if(l<=mid) flag=ask(p<<1,l,r);
if(r>mid) flag=ask(p<<1|1,l,r)?flag:0;
return flag;
}
int main()
{
cin>>n;
cin>>first>>a[++cnt];
a[0]=-1,mp[0]=0;//在最前面插入一个点（前面所有的未知年份压缩成一个）
now=first,mem[1]=first,mp[first]=cnt;
for(int i=2;i<=n;i++)
{
int year,rain;
scanf("%d%d",&year,&rain);
if(year-1!=now)//中间不连续
{
a[++cnt]=-1,now++;
mem[cnt]=now,mp[now]=cnt;//插入一个未知点（如果有很多未知的年份也压缩成一个）
}
a[++cnt]=rain,now=year,mem[cnt]=now,mp[now]=cnt;
}
a[++cnt]=-1,now++;
mem[cnt]=now,mp[now]=cnt;//在最后面插入一个点（后面所有的未知年份压缩成一个）
/*for(int i=1;i<=cnt;i++)
cout<<a[i]<<' ';
cout<<endl;
for(int i=1;i<=cnt;i++)
cout<<mem[i]<<' ';
cout<<endl;*/
build(1,1,cnt);
cin>>m;
while(m--)
{
int x,y,ok=1;
scanf("%d%d",&x,&y);
if(y<=x)
{
cout<<"false"<<endl;
continue;
}
int xx=upper_bound(mem+1,mem+cnt+1,x)-mem-1;
int yy=upper_bound(mem+1,mem+cnt+1,y)-mem-1;
x=x<first?0:mp[mem[xx]];
y=mp[mem[yy]];
//cout<<"x:"<<x<<" a[x]:"<<a[x]<<" y:"<<y<<" a[y]:"<<a[y]<<endl;
if(a[x]==-1&&a[y]==-1)//均未知
{
cout<<"maybe"<<endl;
continue;
}
if(a[x]>0&&a[y]>0&&a[x]<a[y])//均已知
{
cout<<"false"<<endl;
continue;
}
if(y-x<1)//特判的情况
{
if(a[x]==-1||a[y]==-1)
cout<<"maybe"<<endl;
else if(a[x]<a[y])
cout<<"false"<<endl;
else cout<<"true"<<endl;
continue;
}
int maxi=query(1,x+1,y-1);//找到中间点的最大降水量
//cout<<"maxi:"<<maxi<<endl;
if(a[x]>0&&a[y]>0)
{
if(maxi>=a[y])
{
cout<<"false"<<endl;
continue;
}
else
{
bool ok=ask(1,x+1,y-1);//看看中间是否有未知的
if(ok) cout<<"true"<<endl;
else cout<<"maybe"<<endl;
}
}
else//一个已知，一个未知
{
if(a[x]>0&&maxi>=a[x])
{
cout<<"false"<<endl;
continue;
}
if(a[y]>0&&maxi>=a[y])
{
cout<<"false"<<endl;
continue;
}
cout<<"maybe"<<endl;
}
}
return 0;
}
1 |
|
P4198 楼房重建
转化成斜率单调递增序列问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//区间最大可修改上升
using namespace std;
const int N=1e5+10;
int n,m;
struct tree
{
double slope;
int num;
}tr[N*4];
//slope维护区间内最大的斜率
//num维护区间内递增斜率序列的长度
int query(int p,int l,int r,double maxn)
{
if(tr[p].slope<=maxn) return 0;//不符合条件
if(l==r) return tr[p].slope>maxn;//递归到叶结点，判断该点斜率是否大于maxn
int mid=(l+r)>>1;
if(tr[p<<1].slope<=maxn)//左子树中的所有点都会被挡住
return query(p<<1|1,mid+1,r,maxn);//找右子树中未被挡住的点
else return query(p<<1,l,mid,maxn)+tr[p].num-tr[p<<1].num;
//右子树中所有点都未被挡住，找左子树中未被挡住的点
}
void modify(int p,int l,int r,int x,int y)
{
if(l==r)
{
tr[p]={1.0*y/x,1};
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(p<<1,l,mid,x,y);
else modify(p<<1|1,mid+1,r,x,y);
tr[p].slope=max(tr[p<<1].slope,tr[p<<1|1].slope);
tr[p].num=tr[p<<1].num+query(p<<1|1,mid+1,r,tr[p<<1].slope);
//左子树递增斜率序列的长度+右子树中递增斜率序列的长度（右子树中算数的斜率应都大于 tr[p<<1].slope）
}
int main()
{
cin>>n>>m;
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
modify(1,1,n,x,y);
printf("%d\n",tr[1].num);
}
return 0;
}
1 | //区间最大可修改上升 |
P2574 XOR的艺术
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
using namespace std;
const int N=200020;
int a[N];
struct segment_tree
{
int l,r,num,mark;
}t[N*4];
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r)
{
t[p].num=a[l];
//cout<<"p:"<<p<<' '<<a[l]<<endl;
return;
}
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].num=t[p*2].num+t[p*2+1].num;
}
void spread(int p)
{
if(t[p].mark)
{
t[p*2].num=(t[p*2].r-t[p*2].l+1)-t[p*2].num;
t[p*2+1].num=(t[p*2+1].r-t[p*2+1].l+1)-t[p*2+1].num;
t[p*2].mark^=1;
t[p*2+1].mark^=1;
t[p].mark=0;
}
}
void change(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r)
{
t[p].num=(t[p].r-t[p].l+1)-t[p].num;
t[p].mark^=1;
return;
}
int mid=(t[p].l+t[p].r)>>1;
spread(p);
if(l<=mid) change(p*2,l,r);
if(mid<r) change(p*2+1,l,r);
t[p].num=t[p*2].num+t[p*2+1].num;
}
int ask(int p,int l,int r)
{
if(t[p].l>=l&&t[p].r<=r)
return t[p].num;//如果完全包含，返回区间
int mid=(t[p].l+t[p].r)/2;
int ans=0;
spread(p);//下传标记
if(l<=mid) ans+=ask(p*2,l,r);//继续向下
if(r>mid) ans+=ask(p*2+1,l,r);
return ans;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%1d",&a[i]);
build(1,1,n);
while(m--)
{
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1) cout<<ask(1,l,r)<<endl;
if(op==0) change(1,l,r);
}
return 0;
}
1 |
|
P3374 【模板】树状数组 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
long long c[1000010];
int lowbit(int x)
{
return x&(-x);
}
void update(int j,int n,int x)
{
for(int i=j;i<=n;i+=lowbit(i))
{
c[i]+=x;
}
}
long long getsum(int add)
{
long long ans=0;
for(int i=add;i;i-=lowbit(i))
{
ans+=c[i];
}
return ans;
}
int main()
{
int n,q,i;
cin>>n>>q;
for(i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
update(i,n,a);
}
while(q--)
{
int op;
cin>>op;
if(op==1)
{
int j,x;
cin>>j>>x;
update(j,n,x);
}
if(op==2)
{
int l,r;
cin>>l>>r;
long long sum;
sum=getsum(r)-getsum(l-1);
//cout<<"L"<<getsum(l-1)<<endl;
//cout<<"R"<<getsum(r)<<endl;
cout<<sum<<endl;
}
}
return 0;
}
1 |
|
P3368 【模板】树状数组 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
long long a[500005],dif[500005],c[500005];
int n,m;
int lowbit(int x)
{
return x&(-x);
}
void update(int x,long long p)
{
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=p;
}
long long get_sum(int x)
{
long long sum=0;
for(int i=x;i;i-=lowbit(i))
sum+=c[i];
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
while(m--)
{
int option;
scanf("%d",&option);
if(option==1)
{
int front,tail;
long long z;
scanf("%d%d%lld",&front,&tail,&z);
update(front,z);
update(tail+1,-z);
}
if(option==2)
{
int q;
scanf("%d",&q);
cout<<get_sum(q)+a[q]<<endl;
}
}
return 0;
}
1 |
|
P1908 逆序对
树状数组也能写，这里就贴古早学习的归并排序了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using namespace std;
int temp[500005],a[500005],n;
long long ans;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void merge(int l,int r)
{
if(l==r) return;
int mid=(l+r)/2;
merge(l,mid);
merge(mid+1,r);
int i=l,j=mid+1,p=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
temp[p++]=a[i++];
else
ans+=(mid-i+1),
temp[p++]=a[j++];
}
while(i<=mid)
temp[p++]=a[i++];
while(j<=r)
temp[p++]=a[j++];
for(int k=l;k<=r;k++)
a[k]=temp[k];
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
merge(1,n);
cout<<ans;
return 0;
}
1 |
|
P1966 [NOIP2013 提高组] 火柴排队
离散化+求逆序对数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
const int N=1e5+10;
const int mod=1e8-3;
int a[N],b[N],d[N],e[N],pos[N],n;
long long c[N];
long long ans;
int lowbit(int x)
{
return x&(-x);
}
long long ask(int p)
{
long long ret=0;
for(int i=p;i;i-=lowbit(i))
ret+=c[i];
return ret;
}
void add(int p)
{
for(int i=p;i<=n;i+=lowbit(i))
c[i]++;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&d[i]),a[i]=d[i];
for(int i=1;i<=n;i++)
scanf("%d",&e[i]),b[i]=e[i];
sort(d+1,d+n+1);
sort(e+1,e+n+1);
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(d+1,d+n+1,a[i])-d;
//cout<<"a[i]:"<<a[i]<<' ';
pos[a[i]]=i;
b[i]=lower_bound(e+1,e+n+1,b[i])-e;
//cout<<"pos["<<a[i]<<"]="<<i<<endl;
//cout<<"b[i]"<<b[i]<<' ';
}
for(int i=1;i<=n;i++)
b[i]=pos[b[i]];
for(int i=1;i<=n;i++)
{
ans+=ask(n)-ask(b[i]);
//cout<<"ans:"<<ans<<' ';
ans%=mod;
add(b[i]);
}
/*cout<<endl;
memset(c,0,sizeof(c));
for(int i=n;i;i--)
{
ans+=ask(b[i]);
cout<<"ans:"<<ans<<' ';
ans%=mod;
add(b[i]);
}*/
cout<<ans;
return 0;
}
1 |
|
P5677 [GZOI2017]配对统计
一个数能与它形成好配对的一定是和它差值最小的数。顺着这个思路我们可以考虑将数列排序，排序后对于一个数字能与其匹配的只有它左边或右边的数，对于 1 和 n 的情况进行特判，如果两边差值相等就都是好配对。
现在问题就转化为给定一些配对找在$[l,r]$这段区间中有几个好配对，对于这个问题，由于题目并未强制在线，我们可以考虑将询问离线保存，重新排序（按右端点大小）。
1 |
|
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Related Articles
Comment