hdu - 6406 Taotao Picks Apples(离线+离散+技巧)

题目链接：Taotao Picks Apples

题目大意：有n个数，m个操作，每个操作x,q,将x位的数字改为q，输出改完数后数组的递增序列有多长（只能从第一个数开始找，并且必须依次找更大的数）。

思路：我是用离线的方法，先记录x位置之前的有多少个数，然后再求x之后有多少个数，然后输出就行了，之前的好算，之后的不是太好算。
之后的算法：
先用离散这n个数和更改的数，并且将最大的数离散为最小的数，按照求最长严格递增序列的长度来计算，但是要改一下，用lower_bound查找位置的时候，将这个位置之后的数都舍弃（就是这一点没有想到，结果当时没有AC，绝望）。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1e6+9;
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
typedef long long ll;

int a[maxn];
int b[maxn];
int c[maxn*2];
int d[maxn];
int vis[maxn];
struct node
{
    int x,y,h,sum;
} f[maxn];
vector<int>q[maxn];

int main()
{
    int t;
    int n,m;
    scanf("%d",&t);
    while(t--)
    {
        mem(vis,0);
        mem(a,0);
        mem(b,0);
        mem(c,0);
        mem(d,0);
        scanf("%d%d",&n,&m);
        int k=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            c[k++]=a[i];
            q[i].clear();
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&f[i].x,&f[i].y);
            f[i].h=f[i].sum=0;
            c[k++]=f[i].y;
            q[f[i].x].push_back(i);
            vis[f[i].x]=1;
        }
        sort(c,c+k);
        k=unique(c,c+k)-c;
        int sum=0;
        int h=0;
        for(int i=0; i<=n; i++)
        {
            if(a[i]>h)
            {
                h=a[i];
                sum++;
            }
            if(vis[i+1])
            {
                for(int j=0; j<q[i+1].size(); j++)
                {
                    f[q[i+1][j]].sum=sum;
                    f[q[i+1][j]].h=h;
                    if(f[q[i+1][j]].y>h)
                    {
                        f[q[i+1][j]].sum++;
                        f[q[i+1][j]].h=f[q[i+1][j]].y;
                    }
                }
            }
        }
        for(int i=1; i<=n; i++)
            b[n-i+1]=k-(lower_bound(c,c+k,a[i])-c);
        int p=0;
        for(int i=1; i<=n+1; i++)
        {
            if(vis[n-i+1])
            {
                for(int j=0; j<q[n-i+1].size(); j++)
                {
                    int p1=lower_bound(c,c+k,f[q[n-i+1][j]].h)-c;
                    int ff=lower_bound(d,d+p,k-p1)-d;
                    f[q[n-i+1][j]].sum+=ff;
                }
            }
            if(i==n+1) break;
            int p1=lower_bound(d,d+p,b[i])-d;
            d[p1]=b[i];
            p=p1+1;
        }
        for(int i=1; i<=m; i++)
            printf("%d\n",f[i].sum);
    }
    return 0;
}