[USACO17FEB]Why Did the Cow Cross the Road III P
2024-10-17 16:20:41
[USACO17FEB]Why Did the Cow Cross the Road III P
考虑我们对每种颜色记录这样一个信息 \((x,y,z)\),即左边出现的位置,右边出现的位置,该颜色。
于是统计的是\(x < x_2,y > y_2,|z - z2| > k\)的数对数量。
因为\(CDQ\)分治的过程是,第一维事先排序,第二维递归进行,第三维用数据结构统计,所以
上述这个数量是很好处理的。
// Problem: P3658 [USACO17FEB]Why Did the Cow Cross the Road III P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3658
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#define ll long long
#define N 1000010
ll n,k,ans;
ll to[N];
struct P{
int x,y,z;
}a[N],b[N];
bool operator < (P aa,P bb){
return aa.x == bb.x ? ((aa.y == bb.y) ? (aa.z < bb.z) : aa.y > bb.y) : aa.x < bb.x;
}
ll t[N];
#define lowbit(x) (x & -x)
inline void add(int x,int u){
for(int i = x;i <= n;i += lowbit(i))
t[i] += u;
}
inline ll q(int x){
x = std::max(x,0);
x = std::min(n,(ll)x);
ll ans = 0;
for(int i = x;i;i -= lowbit(i))
ans += t[i];
return ans;
}
//_________BIT
#define mid ((l + r) >> 1)
inline void change(int l,int r){
if(l == r)return;
int i = l,j = mid + 1,p = l - 1;
while(i <= mid && j <= r){if(a[i].y > a[j].y)b[++p] = a[i++];else b[++p] = a[j++];}
while(i <= mid)b[++p] = a[i++];
while(j <= r)b[++p] = a[j++];
for(int k = l;k <= r;++k)
a[k] = b[k];
}
inline void solve(int l,int r){
if(l == r)return ;
solve(l,mid);solve(mid + 1,r);change(l,mid);change(mid + 1,r);
int i = l,j = mid + 1;
while(j <= r){
while(i <= mid && a[i].y > a[j].y)add(a[i++].z,1);
ans = ans + (ll)q(a[j].z - k - 1) + (ll)q(n) - (ll)q(a[j].z + k);
++j;
}
for(int k = l;k < i;++k)
add(a[k].z,-1);
}
//————————————————————cdq
int main(){
scanf("%lld%lld",&n,&k);
for(int i = 1;i <= n;++i){
ll x;
scanf("%lld",&x);
to[x] = i;
}
for(int i = 1;i <= n;++i){
ll x;
scanf("%lld",&x);
a[i].x = to[x],a[i].y = i,a[i].z = x;
}
std::sort(a + 1,a + n + 1);
solve(1,n);
std::cout<<ans<<std::endl;
return 0;
}
最新文章
- 基于ASP.Net +easyUI框架上传图片,判断格式+实现即时浏览
- 解决Cygwin中vim的backspace不能正常使用(转)
- 【转】Android fill_parent和wrap_content分析
- POJ3254Corn Fields(状压DP)
- Nginx 安装成 Windows 服务
- SpringMVC:学习笔记(8)——文件上传
- Java标准注释配置
- FPGA在其他领域的应用(二)
- ftp上传文件,本地安装了,服务器上也需要在也安装一个ftp
- 在Visual Studio2017和2015中开发报表项目
- Andorid之页面布局优化
- 临时的ThisCall
- shiro学习总结
- [No000017A]改善C#程序的建议3:在C#中选择正确的集合进行编码
- windows包管理器chocolatey
- HTML5新特性之文件和二进制数据的操作
- java学习-GET方式抓取网页(UrlConnection和HttpClient)
- C++ 函数的扩展①
- ios入门第一天
- Openstack(Kilo)安装系列之neutron(九)