这几天过年啊，过年就不想学啊。。。

这也是没办法的事嘛，这两天的题其实有几个可以写一写，不过多是昨天的CF题，明天再把那一套补一补吧。。。。还有FFT。。。。

又要咕CSAPP。。。

HDU-4911 Inversion

后来想想其实不难看出，只交换相邻两项的话，最多只能去掉一个逆序对。。而且一定能去掉一个逆序对。。。

所以这个问题变成了如何求逆序对。。。

上网一查需要树状数组，看懂了后发现这个题给的 a 是1e9大小。。。

所以很自然的就想到了离散化，巧了，离散化我会啊233333

但是写得第一个版本竟然被t了，我还不知道为什么，又是玄学问题艹艹艹，因为我按原思路又写了一遍就过了，这不是玄学是什么

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
struct node{
    int p;
    ll v;
}a[N];
int h[N];
int c[N];
bool cmp(node n,node m){
    return n.v<m.v;
}
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    for(int i=x;i<=N;i+=lowbit(i))
        h[i]++;
}
ll ask(int x)
{
    ll ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans+=h[i];
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    ll n,k;
    while(cin>>n>>k)
    {
        memset(h,0,sizeof(h));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].v;
            a[i].p=i;
        }
        sort(a+1,a+n+1,cmp);
        c[a[1].p]=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i].v==a[i-1].v){
                c[a[i].p]=c[a[i-1].p];
            }
            else c[a[i].p]=i;
        }
        ll ans=0;
        for(int i=n;i>=1;i--)
        {
            ans+=ask(c[i]-1);
            add(c[i]);
        }
        cout<<max(ans-k,(ll)0)<<endl;;
    }
}

HDU-1506 Largest Rectangle in a Histogram

原本想做完这个题就去打游戏，结果从b站看雪乃看到忘记时间。。。然后他们就ak了。。。。艹

这个题可以dp可以单调栈，其实性质差不多啦，这个单调栈真的很像dp。。。

看单调栈得博客真的把我看懵了，还是直接看代码好理解。。

首先先引入一个概念叫宽度，在这个题中，对于一个小区间的矩形，它的左边高于它的矩形的个数加上1（它自身）就是它的左宽，右边高于它的矩形的个数就是它的右宽

这个题让求最大的矩形嘛，其实换个思路，枚举每一个小区间的矩形，这个矩形所形成的最大矩形就是它的总宽乘上高度，所以找所有矩形中最大的那个就行了

但是这样直接找复杂度不稳定，随便一卡就超时，于是就用到了单调栈，因为（递增）单调栈有这些性质：

  1. 从左到右单调递增
  2. 如果当前读到的元素大于栈顶元素就直接插入，而且它的左宽为1（它自身）
  3. 如果当前读到的元素小于栈顶元素就将栈里大于当前元素的元素都出栈
  4. 第一个出栈元素的右宽一定为0
  5. 后面出栈元素的右宽为前一个出栈元素的总宽
  6. 找到第一个栈顶元素小于当前元素后，当前元素入栈，左宽为直方图中它到第一个小于当前元素中所有元素的个数加上它本身，即最后一个出栈元素的总宽加上1（它自身）

有了这些就可以做出来这个题啦

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int a[N];
int w[N];   //左宽
int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n){
        if(n==0)break;
        int top=0;
        memset(a,-0x3f,sizeof(a));
        memset(w,0,sizeof(w));
        ll ans=0;
        for(int i=1;i<=n+1;i++){
            int h=0;
            if(i!=n+1)cin>>h;
            if(h>a[top]){
                a[++top]=h;
                w[top]=1;
            }
            else {
                int cnt=0;  //当前右宽，前一个总宽
                while(h<=a[top]){
                    ans=max(ans,(ll)(w[top]+cnt)*a[top]);
                    cnt+=w[top--];//当前右宽等于前一个
                }                 //右宽加上前一个左宽
                a[++top]=h;
                w[top]=cnt+1;
            }
        }
        cout<<ans<<endl;
    }
}