Processing math: 100%
  1. 1 Refrain Anan Ryoko
  2. 2 镇命歌 -しずめうた- 瀧沢一留
  3. 3 Pure SCHAT10(影)
  4. 4 Lemon Soda NGC 3.14/Tenkitsune
  5. 5 summer vibe Cyan Lpegd
  6. 6 DJ Okawari - Flower Dance(钢琴原版) Oturans
  7. 7 花降らし n-buna/初音ミク
  8. 8 Lemon 米津玄師
  9. 9 明けない夜、醒めない夢 Yunomi
  10. 10 ニゲラの花束 鎖那
  11. 11 ひだまりの郷 八乙女葦菜
  12. 12 Pneumatic Tokyo EnV
  13. 13 摘星座的女孩 Rainbowets
Refrain - Anan Ryoko
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

noi.ac 36 列队 题解

题意简述

有一个n×m的矩阵a,每个数是[1,n×m]之间的整数,并且互不相同。然后有Q次询问,每次询问给定x,y,问你有多少个数满足:它在行中是第x大,在列中是第y大。

n,m<=1000,Q<=5e5

思路框架

x[i][j]表示a[i][j]在第i行里第几大,y[i][j]表示a[i][j]在第j列第几大。
ans[i][j]表示在行里排第i大,列里排第j大的数有多少。对于所有i,jans[x[i][j]][y[i][j]++。

每次询问输出ans[x][y]即珂。O(nmlog(n+m)+Q)

x[i][j]y[i][j],您珂以用一个lowerbound解决,或者像我一样sb的写一个树状数组。

代码

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
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
#define N 1333
#define F(i,l,r) for(int i=l;i<=r;++i)
#define D(i,r,l) for(int i=r;i>=l;--i)
#define Fs(i,l,r,c) for(int i=l;i<=r;c)
#define Ds(i,r,l,c) for(int i=r;i>=l;c)
#define MEM(x,a) memset(x,a,sizeof(x))
#define FK(x) MEM(x,0)
#define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
#define p_b push_back
#define sz(a) ((int)a.size())
#define iter(a,p) (a.begin()+p)
void R1(int &x)
{
x=0;char c=getchar();int f=1;
while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=(f==1)?x:-x;
}
void Rd(int cnt,...)
{
va_list args;
va_start(args,cnt);
F(i,1,cnt)
{
int* x=va_arg(args,int*);R1(*x);
}
va_end(args);
}
class BIT
{
public:
int tree[N*N];
int len;
void BuildTree(int _len)
{
len=_len;
FK(tree);
}
void Add(int pos,int val=1)
{
for(int i=pos;i<=len;i+=(i&(-i)))
{
tree[i]+=val;
}
}
int Query(int pos)
{
int ans=0;
for(int i=pos;i>0;i-=(i&(-i)))
{
ans+=tree[i];
}
return ans;
}
}T;
int n,m,q;
int a[N][N];
void Input()
{
Rd(3,&n,&m,&q);
F(i,1,n) F(j,1,m) R1(a[i][j]);
}

int line[N][N],col[N][N];
int ans[N][N];
void Soviet()
{
T.BuildTree(n*m);
F(i,1,n)
{
F(j,1,m) T.Add(a[i][j],1);
F(j,1,m) line[i][j]=m-T.Query(a[i][j])+1;
F(j,1,m) T.Add(a[i][j],-1);
}
F(j,1,m)
{
F(i,1,n) T.Add(a[i][j],1);
F(i,1,n) col[i][j]=n-T.Query(a[i][j])+1;
F(i,1,n) T.Add(a[i][j],-1);
}

F(i,1,n) F(j,1,m) ans[line[i][j]][col[i][j]]++;
F(i,1,q)
{
int x,y;Rd(2,&x,&y);
printf("%d\n",ans[x][y]);
}
}

#define Flan void
Flan IsMyWife()
{
Input();
Soviet();
}
}
int main()
{
Flandre_Scarlet::IsMyWife();
getchar();getchar();
return 0;
}
w