0%

[MZOI2019]老爷爷无药可救命题报告

摘要:之前的数据太小被syc大佬暴力过了…

[MZOI2019]老爷爷无药可救

题面

题目分析

这题是我去年出的了.

简单描述下题意,给定两个长度为n序列a,b,a中的元素大小不超过k,m次询问,每次询问[l,r]区间中a序列中众数的每个下标对应在b序列上的和,$n,m,k \leq 100000$.

首先说明求众数只是为了增加码长,分块求即可,你们别骂我了(句号)

然后是考虑求出众数之后如何求和,考虑到a的值域,这里使用主席树.

将主席树建在a的值域上,把b序列作为主席树的历史版本,每次在主席树上新开一个历史版本,b就加在对应位置的a上面(注意是a的值不是a的下标).

然后在询问的时候,先用分块求出众数,用右端点的历史版本上众数对应b的和减去左端点的历史版本上众数对应b的和就是答案了.

代码

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
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "cmath"
#include "vector"
#include "map"
#include "vector"
#include "time.h"
#define lxl long long
#define R register
#define INF 2147483647
#define debug(x) printf("debug:%lld\n",x)
using namespace std;
const lxl maxn=100010;
lxl n,len,id,k,m;
lxl a[maxn],bl[maxn],block[maxn],num[maxn],Max[2010][2010],val[maxn],times[maxn];
bool flag[maxn];
vector<lxl>v[maxn];
map<lxl,lxl>Map;
struct _Number
{
lxl num,times;
};
struct _SegmentTreeNode
{
_SegmentTreeNode *lson,*rson;
lxl l,r,sum;
}*root[maxn];
struct _SegmentTree
{
void BulidTree(_SegmentTreeNode *t,lxl l,lxl r)
{
lxl mid((l+r)>>1);
t->l=l,t->r=r;
if(l==r)
{
t->lson=t->rson=NULL;
return;
}
t->lson=new _SegmentTreeNode,t->rson=new _SegmentTreeNode;
BulidTree(t->lson,l,mid),BulidTree(t->rson,mid+1,r);
t->sum=(t->lson->sum+t->rson->sum);
}
_SegmentTreeNode *insert(_SegmentTreeNode *t,lxl l,lxl r,lxl x,lxl val)
{
lxl mid((l+r)>>1);
_SegmentTreeNode *p=new _SegmentTreeNode;
p->lson=t->lson,p->rson=t->rson,p->l=t->l,p->r=t->r,p->sum=t->sum+val;
if(l==r)return p;
if(x<=mid)p->lson=insert(t->lson,l,mid,x,val);
else p->rson=insert(t->rson,mid+1,r,x,val);
return p;
}
lxl query(_SegmentTreeNode *t,lxl l,lxl r,lxl x)
{
lxl mid((l+r)>>1);
if(l==r)return t->sum;
if(x<=mid)return query(t->lson,l,mid,x);
else return query(t->rson,mid+1,r,x);
}
}SegmentTree;
inline lxl read(){char c=getchar();lxl f=1,output=0;for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())output=(output<<1)+(output<<3)+c-'0';return output*f;}
inline void prework(lxl x)
{
lxl max_=0,cnt=0;
memset(times,0,sizeof(times));
for(lxl i=(x-1)*len+1;i<=n;i++)
{
times[num[i]]++;
if(times[num[i]]>cnt||times[num[i]]==cnt&&val[num[i]]<val[max_])
{
cnt=times[num[i]];
max_=num[i];
}
Max[x][block[i]]=max_;
}
}
inline lxl GetTimes(lxl id,lxl x,lxl y)
{
return upper_bound(v[id].begin(),v[id].end(),y)-lower_bound(v[id].begin(),v[id].end(),x);
}
inline lxl query(lxl x,lxl y)
{
lxl ans=Max[block[x]+1][block[y]-1];
lxl cnt=GetTimes(ans,x,y);
memset(flag,false,sizeof(flag));
flag[ans]=true;
for(R int i=x;i<=min(block[x]*len,y);i++)
{
if(flag[num[i]]==true)continue;
flag[num[i]]=true;
lxl cnt_=GetTimes(num[i],x,y);
if(cnt_>cnt||cnt_==cnt&&val[num[i]]<val[ans])
{
cnt=cnt_;
ans=num[i];
}
}
if(block[x]!=block[y])
{
for(R int i=(block[y]-1)*len+1;i<=y;i++)
{
if(flag[num[i]]==true)continue;
flag[num[i]]=true;
lxl cnt_=GetTimes(num[i],x,y);
if(cnt_>cnt||cnt_==cnt&&val[num[i]]<val[ans])
{
cnt=cnt_;
ans=num[i];
}
}
}
return val[ans];
}
int main(void)
{
n=read(),k=read(),m=read();
len=80;
for(R int i=1;i<=n;i++)
{
a[i]=num[i]=read();
block[i]=(i-1)/len+1;
if(!Map[num[i]])
{
Map[num[i]]=++id;
val[id]=num[i];
}
num[i]=Map[num[i]];
v[num[i]].push_back(i);
}
for(R int i=1;i<=block[n];i++)prework(i);
root[0]=new _SegmentTreeNode;
SegmentTree.BulidTree(root[0],1,k);
for(R lxl i=1;i<=n;++i)
{
bl[i]=read();
root[i]=SegmentTree.insert(root[i-1],1,k,a[i],bl[i]);
}
for(R int i=1;i<=m;i++)
{
lxl l=read(),r=read();
lxl id=query(l,r);
printf("%lld\n",SegmentTree.query(root[r],1,k,id)-SegmentTree.query(root[l-1],1,k,id));
}
return 0;
}