Price List

题意：

有n件商品，每天只能买一件，并且会记录账本，问有多少次一定记多了？

题解：

就是求和，最后如果大于和就输出1，否则0。

代码：

#include 
    
     using namespace std;typedef long long ll;#define SI(N) cin>>(N)#define SII(N,M) cin>>(N)>>(M)#define rep(i,b) for(int i=0;i<(b);i++)int n,m;int main(){    int o;    SI(o);    while(o--)    {        SII(n,m);        ll sum=0,a;        rep(i,n) SI(a),sum+=a;        rep(i,m)        {            SI(a);            if (a>sum) putchar('1');            else putchar('0');        }        puts("");    }    return 0;}
    

NanoApe Loves Sequence（线段树）

题意：

在数学课上，NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为 n 的数列，他又根据心情随便删了一个数，这样他得到了一个新的数列，然后他计算出了所有相邻两数的差的绝对值的最大值。

他当然知道这个最大值会随着他删了的数改变而改变，所以他想知道假如全部数被删除的概率是相等的话，差的绝对值的最大值的期望是多少。

题解：

这题可以简单的模拟下，先求出最大值，并记录位置，之后枚举每个要删除的数字，与最大值比较就好，但其中一定会到一个影响最大值的数字，这时候，重新算遍最大值就好了。这是精简的算法，我想的是线段树，有些麻烦：先算出各位之差，之后删除1个点会修改2个绝对值，之后在查询最大值，ans+=最大值，最后不要忘了在更新回来。

代码：

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 100000+9;int MAX[maxn<<2];int inp[maxn];int iab[maxn],cntb;void PushUP(int rt) {    MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);}void build(int l,int r,int rt) {    if (l == r) {        MAX[rt]=iab[cntb++];        return ;    }    int m = (l + r) >> 1;    build(lson);    build(rson);    PushUP(rt);}void update(int p,int sc,int l,int r,int rt) {    if (l == r) {        MAX[rt] = sc;        return ;    }    int m = (l + r) >> 1;    if (p <= m) update(p , sc , lson);    else update(p , sc , rson);    PushUP(rt);}int query(int L,int R,int l,int r,int rt) {    if (L <= l && r <= R) {        return MAX[rt];    }    int m = (l + r) >> 1;    int ret = 0;    if (L <= m) ret = max(ret , query(L , R , lson));    if (R > m) ret = max(ret , query(L , R , rson));    return ret;}int main() {    int o;    scanf("%d",&o);    while(o--)    {        memset(iab,0,sizeof(iab));        int n;        scanf("%d",&n);        for(int i=1;i<=n;i++)        {            scanf("%d",&inp[i]);        }        for(int i=1;i<=n-1;i++)        {            iab[i]=abs(inp[i+1]-inp[i]);        }        cntb=1;        n-=1;        build(1,n,1);        ll ans=0;        ans+=query(2 , n , 1 , n , 1);        for(int i=2;i<=n;i++)        {            update(i, abs(inp[i+1]-inp[i-1]), 1 , n , 1);            update(i-1, abs(inp[i+1]-inp[i-1]), 1 , n , 1);            int d=query(1 , n , 1 , n , 1);            update(i, abs(inp[i+1]-inp[i]), 1 , n , 1);            update(i-1, abs(inp[i]-inp[i-1]), 1 , n , 1);            ans+=d;        }        ans+=query(1 , n-1 , 1 , n , 1);        printf("%I64d\n",ans);    }    return 0;}
      
     
    

NanoApe Loves Sequence Ⅱ（尺取法）

题意：

在数学课上，NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为 n 的数列，他又根据心情写下了一个数 m。

他想知道这个数列中有多少个区间里的第 k 大的数不小于 m，当然首先这个区间必须至少要有 k 个数啦。

题解：

首先你要知道，这是尺取法的问题。你要有这么一个思维转换：求第k大的数不小于m也就相当于有k个数是大于等于m的，那么这题用尺取法也就很简单了，最后注意ans的取法，ans+=n-尾指针，int会溢出，所以用ll，以后答案尽量用ll，因为int总是容易爆

代码：

#include 
    
     using namespace std;typedef long long ll;const int MAXN= 200000 + 9 ;int a[MAXN];int n,m,k;int main(){    int o;    scanf("%d",&o);    while(o--)    {        scanf("%d%d%d",&n,&m,&k);        for(int i=0; i
     
      =m)                cnt++;            if (cnt==k)            {                while(a[nex]