洛谷P 110[ZJOI 2007]レポート統計解題レポート

P 110[ZJOI 2007]レポート統計

タイトルの説明

(Q)のお母さんは出納で、よく統計報告書の仕事をしなければなりません.今日はお母さんの诞生日で、小さい(Q)はお母さんにいくつかの仕事を分担することができることを望んで、彼女の诞生日の赠り物の1つとします.
よく観察すると、小(Q)は、統計レポートが実際に非負の整数数列を維持し、いくつかのクエリー操作を行うことを発見しました.
最初に、長さNの整数シーケンスがあり、次の3つの操作があります.
(INSERT)(i)(k):元の列のi番目の要素の後ろに新しい要素を追加します(k);元の列の(i)番目の要素にいくつかの要素が追加されている場合、これらの要素の最後に追加されます(次の例を参照)(MIN_GAP):隣接する2つの要素の間の差(絶対値)の最小値をクエリーします(MIN_SORT_GAP):すべての要素の中で最も近い2つの要素の差(絶対値)をクエリーします.たとえば、最初のシーケンスは5,3,1です.
実行操作(INSERT)2 9は、5,3,9,1が得られ、この場合(MIN_GAP)は2、(MIN_SORT_GAP)は2となる.
再実行操作(INSERT)2 6は、5,3,9,6,1を得る
このとき、元のシーケンスの2番目の要素の後ろに9が追加されていることに注意してください.このとき、追加された6は9の後ろに追加されます.このとき(MIN_GAP)は2、MIN_SORT_GAPは11です.
そこでQさんはプログラムを書いて、プログラムが自動的にこれらの操作を完成させることができますが、彼はいくつかの大きなレポートに対して彼のプログラムが遅く実行されていることを発見しました.あなたは彼のプログラムを改善することができますか?

にゅうしゅつりょくけいしき

入力形式:

最初の行には、2つの整数(N)、(M)が含まれ、それぞれ元の列の長さと操作の回数を表します.
2番目の動作(N)の整数は、初期シーケンスです.
次の(M)行は、行ごとに1つのアクション、すなわち(INSERT)(i)(k),(MIN_GAP),(MIN_SORT_GAP)のうちの1つ(余分なスペースや空の行がない)です.

出力フォーマット:

各(MIN_GAP)と(MIN_SORT_GAP)コマンドに対して、1行の答えを出力します.

説明

30%のデータに対して、N≦1000、M≦5000は100%のデータに対して、N、M≦500000はすべてのデータに対して、シーケンス内の整数は5*10^8を超えない.
時限2 s
さあ、やれ!木を2本打つようだ.
疲れてはいけない...
set水を1粒持ってきてください.へへ.の
そして繰り返しを処理することを発見して、setは自動的に重くなって、構造体の保存回数を書きたいと思って、1つの重さを書くかもしれないことを発見してfindに1つの等しい番号を書いてfindに使うことを発見して、しかし私はfindがこれに基づいているかどうか分からないで、multisetを調べて、しかしこのはっきりしているのは意外にも回数でクリアしたので、仕方がなくて、暴力は少し
ツリー1のメンテナンス(dat)ドメインは、2つの数の差です.ツリー2(dat)ドメインのメンテナンス数のサイズは、削除されていないため、新しいポイントを追加するたびに前駆orの後続更新を検索すればよい.

#include 
#include 
#define ls t[now].ch[0]
#define rs t[now].ch[1]
#define s t[now].ch[typ]
#define f t[now].par
using namespace std;
int min(int x,int y){return x0?x:-x;}
const int N=500010;
const int inf=0x3f3f3f3f;
int n,m,root,tot=0,m_min=inf,x;
multiset  tr;
int head[N],tail[N],pos;
char opt[20];
class Splay
{
    public:
        struct node
        {
            int ch[2],par,dat;
        }t[N<<1];
    int identity(int now)
    {
        return t[f].ch[1]==now;
    }
    void connect(int fa,int now,int typ)
    {
        t[fa].ch[typ]=now;
        f=fa;
    }
    void rotate(int now)
    {
        int p=f,typ=identity(now);
        connect(p,t[now].ch[typ^1],typ);
        connect(t[p].par,now,identity(p));
        connect(now,p,typ^1);
    }
    void splay(int now,int to)
    {
        for(to=t[to].par;f!=to;rotate(now))
            if(t[f].par!=to)
                rotate(identity(now)^identity(f)?now:f);
        if(!to) root=now;
    }
    int New(int dat)
    {
        t[++tot].dat=dat;
        return tot;
    }
    int get_max(int now)
    {
        if(!now) return 0;
        return rs?get_max(rs):now;
    }
    int get_min(int now)
    {
        if(!now) return 0;
        return ls?get_min(ls):now;
    }
    void updata(int now)
    {
        int mx=get_max(ls),mi=get_min(rs);
        if(mx) m_min=min(m_min,t[now].dat-t[mx].dat);
        if(mi) m_min=min(m_min,t[mi].dat-t[now].dat);
    }
    void insert(int dat)
    {
        int now=root,typ,last;
        if(!now) {connect(0,root=now=New(dat),1);return;}
        for(;t[now].dat!=dat&&now;last=now,now=s)
            typ=t[now].dat1) add(abs(head[i]-head[i-1]));
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",opt);
        if(opt[0]=='I')
        {
            scanf("%d%d",&pos,&x);
            if(pos

2018.6.14
転載先:https://www.cnblogs.com/butterflydew/p/9184035.html