線段樹；
?//?離散化的線段樹；?
?#include?<?stdio.h?>?
#include?<?algorithm?>?
#include?<?memory.h?>?
?using???namespace??std;

?const???int??MAX?=?1100000?;
?int??p[?3?*?MAX];
?int??b[MAX];
?int??c[MAX];
?int??q[?3?*?MAX];
?int??Min[MAX];
?int??Max[MAX];
?class??IntervalTree
??{
?public?:
?????int??n;
????IntervalTree();
?????void???set?(?int??x);
?????int??InsOrDel(?int??x,?int??test);
?????int??FMAX();
?????int??FMIN();
?????int??Find(?int??x);
}?;
IntervalTree::IntervalTree()
??{
????memset(p,?0?,?sizeof?(p));
}?
?void??IntervalTree::?set?(?int??m)
??{
????n?=?m;
?????/**/?/*?initial?n?to?the?smallest?number；?
????????int?k=Insert(1,1);
????for(int?i=1;i<=k;i*=2)
????????p[i]=n;
?????????*/?
}?
?int??IntervalTree::InsOrDel(?int??x,?int??test)?//?test=1,add;test=0,delete;?
???{
?????int??left?=?0?,right?=?n;
?????int??k?=?1?;
?????int??mid;
?????while?(left?<?right)
??????{
????????mid?=?(left?+?right)?>>?1?;
?????????if?(test?>?0?)
????????????p[k]?++?;
?????????else??p[k]?--?;
?????????if?(x?<=?c[mid])??{
????????????k?<<=?1?;
????????????right?=?mid;
????????}?
??????????else??{
????????????k?<<=?1?;
????????????k?++?;
????????????left?=?mid?+?1?;
????????}?
????}?
??????if?(test?>?0?)??{
????????p[k]?++?;
????????q[k]?=?x;
????}?
??????else??{
????????p[k]?--?;
????}?
?????return??k;
}?
?int??IntervalTree::FMAX()?//?find?the?max;?
???{
?????int??k;
????k?=?1?;
?????while?(p[?2?*?k]?>?0?||?p[?2?*?k?+?1?]?>?0?)??{
?????????if?(p[?2?*?k?+?1?]?>?0?)k?=?2?*?k?+?1?;
?????????else??k?=?2?*?k;
????}?
?????return??q[k];
}?
?int??IntervalTree::FMIN()?//?find?the?min;?
???{
?????int??k;
????k?=?1?;
?????while?(p[?2?*?k]?>?0?||?p[?2?*?k?+?1?]?>?0?)??{
?????????if?(p[?2?*?k]?>?0?)k?=?2?*?k;
?????????else??k?=?2?*?k?+?1?;
????}?
?????return??q[k];
}?
?int??IntervalTree::Find(?int??t)?//?Find?the?index?of?t;?
???{
?????int??left?=?1?,right?=?n;
?????int??mid;
?????int??k?=?1?;
?????while?(left?<?right)??{
????????mid?=?(left?+?right)?>>?1?;
?????????if?(t?<=?p[k])??{
????????????k?<<=?1?;
????????????right?=?mid;
????????}?
??????????else??{
????????????t?-=?p[k];
????????????k?<<=?1?;
????????????k?++?;
????????????left?=?mid?+?1?;
????????}?
????}?
????mid?=?(left?+?right)?>>?1?;
?????if?(p[mid]?==?t)?return??mid;
?????else???return???-?1?;?//?t?isn't?in?the?tree;?
?}?
?int??main()
??{????
????IntervalTree?a;
?????int??l,i;
?????int??max,min;
?????int??k,n;
?????int??m;
?????while?(scanf(?"?%d%d?"?,?&?n,?&?k)?!=?EOF)??{
????????memset(p,?0?,?sizeof?(p));
?????for?(i?=?0?;i?<?n;i?++?)??{
????????scanf(?"?%d?"?,b?+?i);
????????c[i]?=?b[i];
????}?
????sort(c,c?+?n);
?????//?離散化，相同的點合并;?
???????for?(i?=?0?,m?=?0?;i?<?n;i?++?,m?++?)??{
?????????while?(i?<?n?-?1?&&?c[i]?==?c[i?+?1?])i?++?;
????????c[m]?=?c[i];
????}?
????a.?set?(m?-?1?);?//?initial;?
??????return???0?;
}?