[COGS 2479][HZOI 2016]オフセット

7873 ワード

CDQ 分割支配

COGSトランスポートゲート
【タイトル説明】
n個の要素を有するシーケンスが与えられ、要素番号は1~nであり、各要素には3つの属性a,b,cがあり、シーケンス中にi【入力形式】
1行目の整数n nは、シーケンス長を表す.
2行目のn n個の整数は、それぞれa 1〜an a 1〜a nを表す.
3行目のn個の整数は、それぞれb 1〜bnb 1〜bnを表す.
4行目のn個の整数は、それぞれc 1〜cn c 1〜c nを表す.
【出力形式】
答えを表す整数.
【サンプル入力】

【サンプル出力】

【様式解釈】
条件を満たす(i,j)(i,j)は、以下の3対である.
(1,2) ( 1 , 2 )
(1,3) ( 1 , 3 )
(1,4) ( 1 , 4 )
【データ範囲と約定】
30%のデータに対してn≦5000 n≦5000であった.
100%のデータに対して、1≦n≦50000 1≦n≦50000であり、すべてのai、bi、ci a i、b i、c iがそれぞれ3つの1〜n 1〜nの配列を構成することを保証する.
【出所】
HZOI 2016
解題分析
四次元オフセットテンプレートの問題...
もちろんCDQ C Dセットツリーも可能ですが、ここではCDQ C DセットCDQ C D Qの書き方を紹介します.
1 D:ソートによって解決します.(ここで入力順)
二次元:我々のCDQ C DQはbufb u f配列の中でその並べ替え,再帰処理を実現する.[lef,rig][l e f,r i g]区間を同時に処理する場合、[lef,mid][l e f,m i d]区間に1次元が小さいことを示すマークを付ける.
3 D:我々CDQ C DQはbuf 2 b u f 2配列においてその並べ替えを実現する.もちろんbuf 2 b u f 2はbuf b u fに基づいて得られる.
第四次元:BIT B I Tは接頭辞和を維持すればよい.注意:変更、クエリーの条件は、1次元の2 D目が小さいことです.このとき、私たちは打ったマークを利用して判定することができます.
まだ分からない学生はコードを見ることができます...

#include 
#include 
#include 
#include 
#include 
#include 
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 50050
#define File freopen("partial_order.in", "r", stdin), freopen("partial_order.out", "w", stdout)
#define lbt(i) (i & -i)
template <class T>
IN void in(T &x)
{
    x = 0; R char c = gc;
    W (!isdigit(c)) c = gc;
    W (isdigit(c))
    x = (x << 1) + (x << 3) + c - 48, c = gc;
}
struct Node
{
    int a, b, c, d;
    bool typ;
}eve[MX], buf[MX], buf2[MX];
int dot, tree[MX];
long long ans;
namespace BIT
{
    IN void clear(R int now)
    {
        W (now <= dot)
        if(tree[now]) tree[now] = 0, now += lbt(now);
        else return;
    }
    IN void add(R int now)
    {W (now <= dot) ++tree[now], now += lbt(now);}
    IN int query(R int now)
    {
        int ret = 0;
        W (now) ret += tree[now], now -= lbt(now);
        return ret;
    }
}
void cdq2(const int &lef, const int &rig)
{
    if(lef == rig) return;
    int mid = lef + rig >> 1;
    cdq2(lef, mid), cdq2(mid + 1, rig);//         c  ，      b      b 
    int lb = lef, rb = mid + 1, cur = lef;
    W (lb <= mid && rb <= rig)
    {
        if(buf[lb].c < buf[rb].c)
        {
            if(!buf[lb].typ) BIT::add(buf[lb].d);//  a       
            buf2[cur++] = buf[lb++];
        }
        else
        {
            if(buf[rb].typ) ans += BIT::query(buf[rb].d);//  a         
            buf2[cur++] = buf[rb++];
        }
    }
    W (lb <= mid) buf2[cur++] = buf[lb++];
    W (rb <= rig)
    {
        if(buf[rb].typ) ans += BIT::query(buf[rb].d);
        buf2[cur++] = buf[rb++];
    }
    for (R int i = lef; i <= mid; ++i) if(!buf[i].typ) BIT::clear(buf[i].d);
    for (R int i = lef; i <= rig; ++i) buf[i] = buf2[i];
}
void cdq1(const int &lef, const int &rig)//  b
{
    if(lef == rig) return;
    int mid = lef + rig >> 1;
    cdq1(lef, mid), cdq1(mid + 1, rig);//         b  
    int lb = lef, rb = mid + 1, cur = lef;
    W (lb <= mid && rb <= rig)
    {
        if(eve[lb].b < eve[rb].b) buf[cur++] = eve[lb++], buf[cur - 1].typ = false;
        else buf[cur++] = eve[rb++], buf[cur - 1].typ = true;
    }
    W (lb <= mid) buf[cur++] = eve[lb++], buf[cur - 1].typ = false;
    W (rb <= rig) buf[cur++] = eve[rb++], buf[cur - 1].typ = true;
    for (R int i = lef; i <= rig; ++i) eve[i] = buf[i];
    cdq2(lef, rig);
}
int main(void)
{
    File;
    in(dot);
    for (R int i = 1; i <= dot; ++i) in(eve[i].b), eve[i].a = i;
    for (R int i = 1; i <= dot; ++i) in(eve[i].c);
    for (R int i = 1; i <= dot; ++i) in(eve[i].d);
    cdq1(1, dot);
    printf("%lld", ans);
}

Appveyor で CMake を使用して MinGW の makefile を作成する際の注意点について

OSXでCMakeを導入してコマンドラインから扱えるようにする