数据结构题
题目：
问在区间[l,r]和[l1,r1]内x的出现次数的乘积是多少？
题解：
莫队算法的模板题 关于莫队算法你可以参考这个 我这里简单的说说我对莫队的理解： 莫队是一个优雅的暴力，就是将原本复杂度不能过的程序进行优化，莫队是通过分块来实现 如果暴力做这个题，查询区间[l,r]内x的数量我们可能就从头开始搜查，按照题目给的数据来搜查，但其实我们可以这样优化,比如题目给的查询区间[3,4],[2,4],[1,5],我们可以先查询[1,5],然后顺势查询[2,4],最后[3,4]，而非从头开始，这样就省了不少时间。那如何实现这个？我们可以对整体进行分块，然后按照所分的快进行排序，尽可能实现查询区间时省时省力，最后再输出答案 至于为什么要分块排序呢？可以看看莫队算法的讲解 很显然这是一个离线算法，且适合查询量很大的情况 代码如下
代码：
#include<bits/stdc++.h>
#define forn(i,a,b) for(ll i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std
;
#define ll long long
const ll N
=100*1000+10;
const ll mod
= 20180623;
ll n
,m
;
ll a
[N
],ans
[N
*2],num
[N
],pos
[N
];
struct node
{
ll L
,R
,x
,id
;
}t
[N
*2];
bool cmp(node a
,node b
){
if(pos
[a
.L
]==pos
[b
.L
])
return a
.R
<b
.R
;
else return pos
[a
.L
]<pos
[b
.L
];
}
ll L
=1,R
=0;
void solve(node p
){
while(p
.L
>L
){
num
[a
[L
]]--;
L
++;
}
while(p
.R
>R
){
R
++;
num
[a
[R
]]++;
}
while(p
.L
<L
){
L
--;
num
[a
[L
]]++;
}
while(p
.R
<R
){
num
[a
[R
]]--;
R
--;
}
}
int main(){
scanf("%lld %lld",&n
,&m
);
memset(num
,0,sizeof(num
));
ll block
=sqrt(n
);
for(ll i
=1;i
<=n
;i
++){
scanf("%lld",a
+i
);
pos
[i
]=i
/block
;
}
for(ll i
=1;i
<=m
;i
++){
ll l1
,r1
,l2
,r2
,x
;
scanf("%lld%lld%lld%lld%lld",&l1
,&r1
,&l2
,&r2
,&x
);
if(l1
>r1
)swap(l1
,r1
);
if(l2
>r2
)swap(l2
,r2
);
t
[i
].L
=l1
;
t
[i
].R
=r1
;
t
[i
].id
=i
;
t
[i
].x
=x
;
t
[i
+m
].L
=l2
;
t
[i
+m
].R
=r2
;
t
[i
+m
].id
=i
+m
;
t
[i
+m
].x
=x
;
}
sort(t
+1,t
+1+2*m
,cmp
);
memset(num
,0,sizeof(num
));
for(ll i
=1;i
<=2*m
;i
++){
solve(t
[i
]);
ans
[t
[i
].id
]=num
[t
[i
].x
];
}
for(ll i
=1;i
<=m
;i
++)
printf("%lld\n%lld\n%lld\n",ans
[i
]%mod
,ans
[i
+m
]%mod
,(ans
[i
]%mod
*ans
[i
+m
])%mod
);
return 0;
}
