二次元偏順&三次元偏順のまとめ
1714 ワード
二次元偏順
星を数えるhttps://loj.ac/problem/10114
大体一次元の順に並べて、二次元の木のような配列を作ってください.値は下付きです.毎回調べる前にいくつかあればいいです.(sum関数)
直接コード
二次元のもとに治療を加えればOKです.まず全部x順に並べて、分割します.そして毎回の答えを+=全体の答えにします.
星を数えるhttps://loj.ac/problem/10114
大体一次元の順に並べて、二次元の木のような配列を作ってください.値は下付きです.毎回調べる前にいくつかあればいいです.(sum関数)
直接コード
#include
using namespace std;
const int maxn=3.2*10005;
struct node
{
int x,y;
}a[maxn];int c[maxn];int n,cnt[maxn];
int maxv=0;
int cmp(node x,node y)
{
if(x.x!=y.x) return x.x0)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].x+=1;a[i].y+=1;
maxv=max(maxv,a[i].y);
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
cnt[sum(a[i].y)]++;
add(a[i].y,1);
}
for(int i=0;i
三次元偏順二次元のもとに治療を加えればOKです.まず全部x順に並べて、分割します.そして毎回の答えを+=全体の答えにします.
#include
using namespace std;
int _n,k;
const int maxn=200005;
struct node
{
int x,y,z,ans,w;
}a[maxn],b[maxn];int n;int c[maxn];
int ans[maxn];
int cmp(node x,node y)
{
if(x.x!=y.x) return x.x0)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)/2;
solve(l,mid);solve(mid+1,r);
sort(a+l,a+mid+1,cmp1);sort(a+mid+1,a+r+1,cmp1);
int i=mid+1;int j=l;
for(;i<=r;i++)
{
while(a[j].y<=a[i].y&&j<=mid) add(a[j].z,a[j].w),j++;
a[i].ans+=sum(a[i].z);
}
for(i=l;i