求逆序对的板子题

 

#include
     
      #define ll long longusing namespace std;const int maxn=1e5+5;ll a[maxn],r[maxn],n;ll ans=0;void msort(ll s,ll t){    if(s==t)        return;    ll mid=s+t>>1;    msort(s,mid),msort(mid+1,t);    ll i=s,j=mid+1,k=s;    while(i<=mid&&j<=t)        if(a[i]<=a[j])            r[k++]=a[i++];        else            r[k++]=a[j++],ans+=(ll)mid-i+1;    while(i<=mid)        r[k]=a[i],k++,i++;    while(j<=t)        r[k]=a[j],k++,j++;    for(int i=s; i<=t; i++)        a[i]=r[i];}inline ll read(){    char ch=getchar();    ll sum=0,k=1;    while(ch<'0'||ch>'9')    {        if(ch=='-')            k=-1;        ch=getchar();    }    while(ch>='0'&&ch<='9')        sum=sum*10+(ch^48),ch=getchar();    return sum*k;}int main(){    scanf("%lld",&n);    for(int i=1; i<=n; i++)        a[i]=read();    msort(1,n);    printf("%lld\n",ans);    return 0;}
     

 

unsigned long long等数据类型的定义方法的巧用

（直接long long居然也可以水到90分.）

#include
     
      using namespace std;int main(){    unsigned long long n;    scanf("%llu",&n);    printf("%llu",n*n);    return 0;}
     

 

单调队列

对于每一个数记录他是第几个放入的

放入时遇到比他小的元素就弹掉

这样保证了队首就是最大值

进行弹出操作时只要关注弹的次数是否等于队首元素id就可以了

（copy大佬的题解）

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int n,num,cnt;deque
         
          
            >q;void solu1(int x,int n){ while(q.size() != 0 && q.back().first< x) { q.pop_back(); } q.push_back(make_pair(x,n));}void solu2(int x){ while(q.front().second <= x && q.size() != 0) q.pop_front();}int main(){ scanf("%d",&n); int opt; for(int i = 1; i <= n; i++) { scanf("%d",&opt); if(opt == 1) { int x; scanf("%d",&x); solu1(x,++num); } if(opt == 2) { solu2(++cnt); } if(q.size() == 0) printf("-1\n"); else printf("%d\n",q.front().first); } return 0;}
          
         
        
       
      
     

 

(大概是我写两个cmp是不对的

（一个就够了qwq）

（于是爆0.

#include
     
      #include
      
       #include
       
        using namespace std;struct shu{    int x,y;};shu c[maxn+5];int n;bool cmp(shu a,shu b){    if(a.x==b.x) return a.y
       
      
     

 

双向队列的基本操作

#include
     
      #include
      
       #include
       
        using namespace std;int n,opt;deque
        
         q;int main(){    scanf("%d",&n);    for(int i = 1; i <= n; i++)    {        scanf("%d",&opt);        if(opt == 1)        {            int x;            scanf("%d",&x);            if(q.size() == 0)                printf("-1\n");            else                printf("%d\n",q.back());            q.push_back(x);        }        else if(opt == 2)        {            if(q.size() == 0)                printf("-1\n");            else            {                printf("%d\n",q.back());                q.pop_back();            }        }        else if(opt == 3)        {            int x,y;            scanf("%d%d",&x,&y);            if(q.size()<=x)                printf("-1\n");            else            {                printf("%d\n",q[x]);                q[x]=y;            }        }        else if(opt == 4)        {            int x;            scanf("%d",&x);            if(q.size() == 0)                printf("-1\n");            else                printf("%d\n",q.front());            q.push_front(x);        }        else if(opt == 5)        {            if(q.size() == 0)                printf("-1\n");            else            {                printf("%d\n",q.front());                q.pop_front();            }        }    }    return 0;}
        
       
      
     

 

 

开两个栈，一个用来模拟真实的栈，另一个求最大值。

每当加入新元素时

如果该元素大于等于栈顶元素 就压进去

弹出元素时，如果真实栈的弹出元素和最大值栈的栈顶元素相等，就弹出。

（qxt好gou啊.

//实现一个栈，支持push和pop，每次执行完毕后要输出栈内元素的最大值#include
     
      #include
      
       using namespace std;stack
       
         q,pq;int n;void solu1(int x){    q.push(x);    if(pq.size() == 0 || pq.top() <= x)        pq.push(x);}void solu2(){    if(q.size())    {        if(pq.size())            if(q.top() == pq.top())            {                q.pop();                pq.pop();            }            else                q.pop();        else            q.pop();    }}int main(){    scanf("%d",&n);    int opt;    for(int i = 1; i <= n; i++)    {        scanf("%d",&opt);        if(opt == 1)        {            int x;            scanf("%d",&x);            solu1(x);        }        if(opt == 2)        {            solu2();        }        if(pq.size() == 0)            printf("-1\n");        else            printf("%d\n",pq.top());    }    return 0;}