蔬菜

Source and Judge

雅礼noip模拟题

问题

给出一个矩阵,q次询问,求一个子矩阵中,每种颜色出现次数的平方和
n和m在200以内,询问在100000以内

Record

1h

Analysis

请先思考后再展开

这道题同时用到了多个思想
显然先离散化一下

有一个子任务,可以给我们启示:颜色种类数比较少
那我们可以给每种颜色处理一个二维前缀和

但如果比较多呢?有一个不好想的做法:对每种颜色的出现次数(总矩阵而言),分类讨论处理办法
如果某种颜色数量多,意味着在总矩阵中份额大
对于数量级达到T的颜色,只有 $\frac{n^2}{T}$ 种,这些是可以预处理前缀和的
但对于零散的颜色,就要用另外一种思想了:平方和转点对数量
也就是说,如果这些颜色的所有点内部形成点对
那么每个询问就转化为一个四维偏序问题(询问为abcd):
$a \leq x1,x2 \leq b;c \leq y1,y2 \leq d$
对于这种类型的颜色,处理所有点对,离线后将点对和询问混合再排序
那么就变成一个三位偏序问题,可以用三维树状数组搞
这里有个细节,因为第一维我们用的是排序,但同时有可以去等,
所以一定将具体类型作为第二关键字

接下来考虑复杂度
零散的颜色即使有n方种,每次往前扫k个形成点对
总时间为 $O(\frac{n^2}{T}(n^2+q)+(q+n^2T) log^3 n)$
考虑均值不等式 $a+b \geq 2 \sqrt{ab}$ ,取等号当且仅当a=b,
列等式计算得 $T=\sqrt{ \frac{n^2+q}{log^3 n} }$
时间复杂度自行验证,通过计算知其也可以通过本题

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
ll mysqr(ll x) {return x*x;}
const int MAX_N=210;
struct Nod{int d,x,y;}s[MAX_N*MAX_N];
bool cmp(Nod a,Nod b) {return a.d<b.d;}
int yz[MAX_N][MAX_N];
#define PR pair<int,int>
#define FR first
#define SE second
vector<PR> old[MAX_N*MAX_N];
int bit[MAX_N][MAX_N][MAX_N];
int lowbit(int x) {return x&-x;}
void change(int x,int y,int z,int d)
{
for(int a=x;a<MAX_N;a+=lowbit(a))
for(int b=y;b<MAX_N;b+=lowbit(b))
for(int c=z;c<MAX_N;c+=lowbit(c))
bit[a][b][c]+=d;
}
int ask(int x,int y,int z)
{
int ans=0;
for(int a=x;a>=1;a-=lowbit(a))
for(int b=y;b>=1;b-=lowbit(b))
for(int c=z;c>=1;c-=lowbit(c))
ans+=bit[a][b][c];
return ans;
}
int tot=0;ll ans[110000];
struct Node{int x1,x2,y1,y2,id;}p[MAX_N*MAX_N*20+100000];//id=询问编号
bool cmp2(Node a,Node b) {return a.x1>b.x1 or (a.x1==b.x1 and a.id<b.id);}
void solve()
{
sort(p+1,p+tot+1,cmp2);
for(int u=1;u<=tot;u++)
{
if(p[u].id==0) change(p[u].x2,p[u].y1,p[u].y2,1);
else ans[p[u].id]+=(ask(p[u].x2,200,p[u].y2)-ask(p[u].x2,p[u].y1-1,p[u].y2));
}
}
int rx;
int num[MAX_N*MAX_N];//count times
int sum[MAX_N][MAX_N];//二维前缀和
void main()
{
int n,m,q;scanf("%d%d%d",&n,&m,&q);
double lg=log2(n);
int k=sqrt( (double)(n*n+q)/lg/lg/lg );//mx=20
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int t;scanf("%d",&t);
s[(i-1)*m+j]=(Nod){t,i,j};
}
sort(s+1,s+n*m+1,cmp);rx=0;
for(int i=1;i<=n*m;i++)
{
if(i==1 or s[i-1].d!=s[i].d) rx++;
yz[s[i].x][s[i].y]=rx;num[rx]++;
}
for(int i=1;i<=q;i++)
{
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
p[++tot]=(Node){a,c,b,d,i};
}
//大量部分
for(int u=1;u<=rx;u++)
{
if(num[u]>=k)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(yz[i][j]==u);
for(int i=1;i<=q;i++)
{
int a=p[i].x1,b=p[i].y1,c=p[i].x2,d=p[i].y2;
ans[i]+=mysqr(sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1]);
}
}
}
//零散部分
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int now=yz[i][j];
if(num[now]<k)
{
old[now].push_back( make_pair(i,j) );
for(int u=0;u<(int)old[now].size();u++)
{
Node tmp=(Node){
min(old[now][u].FR,i),max(old[now][u].FR,i),
min(old[now][u].SE,j),max(old[now][u].SE,j),0};
p[++tot]=tmp;
if(u!=(int)old[now].size()-1) p[++tot]=tmp;//debug 自己算一次
}
}
}
solve();
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c8e3.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%