set和queue的黑科技

最近做了两道STL库黑科技的题。
UESTC - 1339
题意：类似一个队列，有push和pop操作，但是他会问你这个队列的中位数（升序后的k/2+1位数）的值。题目保证每个数字不同。

分析：用一个队列和两个set即可。队列的作用就是模拟队列，set的作用就是存储 中位数以前（l） 和 中位数及中位数以后（r） 的数字。
注意一点，我们在根据这个中位数的位置，可以判断出，只有l==r或者l+1==r两种情况。所以操作的时候注意一下判断即可。

#include<cstdio>
#include<iostream>
#include<queue>
#include<set>

using namespace std;

int main()
{
    queue<int>q;
    set<int>l,r;
    int n;
    scanf("%d",&n);
    set<int>::iterator it;
    while(n--){
        int op,x;
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            q.push(x);
            it=r.begin();
            if(l.size()==r.size()){
                if(x<(*it)){
                    l.insert(x);
                    r.insert(*(--l.end()));
                    l.erase((--l.end()));
                }else{
                    r.insert(x);
                }
            }else{
                if(x<(*it)){
                    l.insert(x);
                }else{
                    l.insert(*it);
                    r.erase(it);
                    r.insert(x);
                }
            }
        }else if(op==2){
            int t=q.front(); q.pop();
            int s=l.size()+r.size();
            it=r.begin();
            if(t>=*it){
                if(s%2==0){
                    r.erase(r.lower_bound(t));
                    r.insert(*(--l.end()));
                    l.erase((--l.end()));
                }else{
                    r.erase(r.lower_bound(t));
                }
            }else{
                if(s%2==0){
                    l.erase(l.lower_bound(t));
                }else{
                    l.insert(*it);
                    l.erase(l.lower_bound(t));
                    r.erase(it);
                }
            }
        }else{
            printf("%d\n",*(r.begin()));
        }
    }
    return 0;
}

1.我看大佬的代码，有提到用l.rbegin()这种函数，不过我自己感觉没有必要。
2.set中find函数的复杂的是O(n)，而lower_bound函数的复杂度是O(logn)的。
3.set是一个自平衡树，是有默认排序的，为升序。同时，一定要用自带的lower_bound函数，因为set不支持随机访问，lower_bound(l.begin,r.begin,x)其实就是一个线性的访问了，与find类似。

还有一种做法是利用 linux的平板电视（pb_ds），不懂，挖坑X1；

福建工程出的一道题。
题目中文，题意下次补；

它用了两个栈来维护乘积。
我模拟一下过程：
首先读入一个l和r。然后从把r个数字入栈，每一个入栈的数字是前i个数字的积。然后执行pop操作——pop操作就是在s2不为空且s1为空的情况下，像s2中投入s1.size（）个数字，第i个数字是[i,r]的乘积。（全部投入就为0-r的乘积，不过是逆序）当然，每一次调用pop会让s2 pop掉一个数字。这样我们执行l次操作，s2的栈顶即为问题的答案。
第二次我们又读入一个nl和nr，此时我们开始扩展s1，扩展方式就是把[r,nr]的乘积投入，第i个投入数字表示[r,i]的乘积。我们目前的状态，s1维护着[r,nr]正序的乘积，s2维护着[l,r]逆序的乘积，而我们知道nl>l 的，所以我们就要开始pop s2，当pop到[nl,r]的逆序乘积时，答案就是s1的栈顶乘s2的栈顶。
当然，第二次可能出现另外一种情况，即为nl>r，但是不用担心，黑科技无敌！！！当出现这种情况时，s1维护的是[r,(nl),nr]的乘积，执行pop时，会将s2的所有数字pop出去，于是s1就会清空，同时像第一步一样，向s2中就开始投入[r,(nl),nr]的逆序乘积，此时刚好又可以pop掉nl-r个数字，所以答案就又为s2的栈顶元素。
就这样一直循环下去的牛逼东西。

但是这种方法是有限制的，只适用于特定的[l,r]。就当奇淫技巧看看吧。
//s2的作用是扩展r1-r2的乘积，通过pop使得s1的栈顶为来l2-r1。
//pop操作也很有意思，其实有用s1控制数量的意思在里面！

#include<bits/stdc++.h>

#define ll long long
#define CLR(x) memset(x,0,sizeof(x))
#define mem(a,x) memset(a,x,sizeof(a))

const int INF = 0x3f3f3f3f;

const ll mod = 1e9+7;
const int maxn = 1e6+100;

using namespace std;

ll Scan()//读入外挂
{
    ll res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
void Out(ll a)//输出外挂
{
    if(a>9)
        Out(a/10);
    putchar(a%10+'0');
}


stack<ll> s1,s2;
ll T,n,p,q;
ll a[maxn];

void pop()
{
    if(s2.empty()){
        while(!s1.empty()){
            if(s2.empty()) s2.push(a[T--]%p);
            else s2.push((a[T--]*s2.top())%p);
            s1.pop();
        }
    }
    s2.pop();
}

void Solve()
{
    n=Scan();
    p=Scan();
    for(ll i=1;i<=n;i++){
        a[i]=Scan();
    }
    q=Scan();
    ll prel=1;
    ll prer=0;
    T=-1;

    for(int i=0;i<q;i++){
        ll l,r;
        l=Scan();
        r=Scan();

        for(int j=prer+1;j<=r;j++){
            if(s1.empty()) s1.push(a[j]%p);
            else s1.push(((a[j]%p)*s1.top())%p);
        }
        T=r;
        for(int j=prel;j<l;j++) pop();
        ll ans;
        if(s1.empty()) ans=s2.top()%p;
        else if(s2.empty()) ans=s1.top()%p;
        else ans=s1.top()*s2.top()%p;
        prel=l; prer=r;
        Out(ans);
        putchar('\n');
    }
}

int main()
{
    //FILEIN
    //FILEOUT
    //std::ios::sync_with_stdio(false);
    int Case=1,cases;
    //scanf("%d", &Case); cases=Case;
    while(Case--){
        //printf("Case #%d:",cases-Case);
        Solve();
    }
    return 0;
}