考试策略

这个里面的花，我看了一下，啊，T2 和 T3 是比较简单的原题啊，匆匆写完过了对拍，看了一下 T4，T4 有思路但是这个离散太恶心了有点思考不清楚，怕写错就打了暴力。T1 完全没思路就打了暴力。

T1

期望得分：20 实际得分：0
题目描述：
我们生活的星球对于整个宇宙来说，只不过是沧海一粟，宇宙到底有多大，到现在还没人知道，其实我们无时无刻不在面临着来自外太空的威胁，当然你也不会知道在我们的身边，有很多人自愿参加了一个叫 FLYIOI 的秘密组织，QZC 就是其中一员，公元 2007 年 4 月 21 日早上 8：00，他截获了一份来自外太空的信息，这份信息是一大串毫无规律的数字，在众多大牛的努力帮助之下，QZC 终于发现这是来自 OIBH 星球的一份密文，由于 QZC 经常去 OIBH 星球参观访问，附带潜水旅游，所以很快知道了他的加密格式。
密文的格式如下：
在第一行有两个数，不妨设为 N，M。
第二行有 N 个数，设为 a1，a2，……，an。
接下来有 M 行，每行有三个数字设为 x，y，z。
如果对于 M 行的每一行 x，y，z，得到一个数字 Q，Q 代表有多少个不同的数字，在 ax…ay 和 ay+1…az 中都不得出现过，将这 M 个数字顺次连起来，就是解密后的信息。保卫世界和平的任务就落在你的肩上了，请你编写一个数字统计程序来解开来自 OIBH 星球的密文。
数据范围：
对于 20% 的数据，N<=1000，M<=1000；
对于 100% 的数据，N<=200000，M<=40000；0<=ai<=Maxlongint。
题目分析：
感谢 pyh 大佬的帮助。
pyh 大佬说，假如某一元素在序列里出现了若干次，位置为 a1,a2…an，我们就在平面上建立点 (a1,a2),(a2,a3),(a3,a4)….[我的思路是离散出现的数字]
然后对于每一个询问 (x,y,z), 建立一个左上角坐标为 (x,z), 右下角坐标为 (y,y+1) 的矩形，然后求里面的点的数量即可。
为什么呢？因为我们要求相同元素的两个区间是相邻的，所以我们从左区间拿一个该元素，右区间拿一个，如果他们中间还有一个该元素，就不会被计算，如果没有，才会被计算。这就皆大欢喜了，不会重复计算元素呢。
那么我们要怎么求呢？pyh 大佬提供的思路是扫描线。对于每一个矩形，我们可以看作是在其右边界限以前的所有点数-在其左边界限以前的所有点数。这样我们把点和矩形的线从小到大排个序后，加点进一个树状数组，加的位置是其 y 坐标的位置，然后看矩形的界限上下 y 坐标统计点的个数，即可很快的求出答案。
最后%%%pyh 大佬。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
const int N=200005,M=40005;
int n,m,cn,ds,bs;
int a[N],b[N],pre[N],in[M],le[M],tr[N];
struct nn{int x,y;}po[N];
struct node{int xx,ll,rr,id,num;}s[M<<1];
bool cmp1(nn s,nn t){return s.x<t.x;}
bool cmp2(node s,node t){return s.xx<t.xx;}
int lowbit(int x){return x&(-x);}//树状数组
void add(int x){while(x<=n)++tr[x],x+=lowbit(x);}
int find(int x){
    int re=0;
    while(x>0)re+=tr[x],x-=lowbit(x);
    return re;
}
void work(){//扫描线
    int now=1,i;
    for(i=1;i<=bs;++i){
        while(po[now].x<=s[i].xx&&now<=ds)add(po[now].y),++now;
        if(s[i].num==1)in[s[i].id]=find(s[i].rr)-find(s[i].ll-1);
        else le[s[i].id]=find(s[i].rr)-find(s[i].ll-1);
    }
    for(i=1;i<=m;++i)printf("%d",le[i]-in[i]);
}
int main(){
    freopen("secret.in","r",stdin);
    freopen("secret.out","w",stdout);
    int i,kx,ky,kz;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    cn=1;for(i=2;i<=n;++i)if(b[i]!=b[cn])b[++cn]=b[i];//离散出现的数字
    for(i=1;i<=n;++i){
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
        if(pre[a[i]])po[++ds].x=pre[a[i]],po[ds].y=i;
        pre[a[i]]=i;
    }
    for(i=1;i<=m;++i){
        scanf("%d%d%d",&kx,&ky,&kz);
        s[++bs].xx=kx-1,s[bs].ll=ky+1,s[bs].rr=kz,s[bs].id=i,s[bs].num=1;//建立扫描线
        s[++bs].xx=ky,s[bs].ll=ky+1,s[bs].rr=kz,s[bs].id=i,s[bs].num=-1;
    }
    sort(po+1,po+1+ds,cmp1);sort(s+1,s+1+bs,cmp2);
    work();
    return 0;
}

T2

期望得分：100 实际得分：100
题目描述：
由于你即将参加选拔赛，会有麻烦的问题等你解决，不过之前，我们还是请你先解决下面的问题，问题很简单：
有一个长度为 L 的长木板，将其均匀的分成 L 段，从 1…L 标号，可以对木板进行下列两种操作
C(A, B, C) 将第 A 段到第 B 段全部涂成颜色 C
P(A, B) 计算第 A 段到第 B 段间不同的颜色数 (包含 A 和 B 段)
颜色从 1..T 开始顺次表示，最开始的时候整个木板被涂成颜色 1。
数据范围：
第一行 L(1≤L≤100000), T(1≤T≤30), O(1≤O≤10000) 表示木板的段数，颜色总数和
操作的个数。接下来 O 行, 每行包含上述两种操作之一。
题目分析：
状态压缩，用一个二进制数来表示一段区间内颜色的集合，最后求出颜色集合，并统计其中颜色个数即可。
有一个坑点，就是数据里有右区间大于左区间的情况，要注意特判。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n,t,m;
int c[N<<2],laz[N<<2],bin[32];
void up(int i){c[i]=c[i<<1]|c[(i<<1)|1];}
void pd(int i){
    int l=(i<<1),r=(i<<1)|1;
    laz[l]=laz[r]=laz[i],c[l]=c[r]=bin[laz[i]];
    laz[i]=0;
}
void chan(int l,int r,int s,int t,int i,int z){
    if(l<=s&&t<=r){laz[i]=z,c[i]=bin[z];return;}
    int mid=(s+t)>>1;
    if(laz[i])pd(i);
    if(l<=mid)chan(l,r,s,mid,i<<1,z);
    if(mid+1<=r)chan(l,r,mid+1,t,(i<<1)|1,z);
    up(i);
}
int query(int l,int r,int s,int t,int i){
    if(l<=s&&t<=r)return c[i];
    int mid=(s+t)>>1,re=0;
    if(laz[i])pd(i);
    if(l<=mid)re=query(l,r,s,mid,i<<1);
    if(mid+1<=r)re=re|query(l,r,mid+1,t,(i<<1)|1);
    return re;
}
void build(int s,int t,int i){
    if(s==t){c[i]=1;return;}
    int mid=(s+t)>>1;
    build(s,mid,i<<1),build(mid+1,t,(i<<1)|1);
    up(i);
}
int find(int x){
    int re=0;
    while(x){x-=(x&(-x));++re;}
    return re;
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int i,x,y,z;char ch[5];
    scanf("%d%d%d",&n,&t,&m);
    build(1,n,1);
    bin[1]=1;
    for(i=2;i<=t;++i)bin[i]=bin[i-1]<<1;
    for(i=1;i<=m;++i){
        scanf("%s",ch);
        if(ch[0]=='C'){
            scanf("%d%d%d",&x,&y,&z);
            if(y<x)swap(x,y);
            chan(x,y,1,n,1,z);
        }
        else {
            scanf("%d%d",&x,&y);
            if(y<x)swap(x,y);
            printf("%dn",find(query(x,y,1,n,1)));
        }
    }
    return 0;
}

T3

期望得分：100 实际得分：100
题目描述：
XXX 最近的旅游计划，是到 XXXX 湖畔，享受那里的湖光山色，以及明媚的阳光。你作为整个旅游的策划者和负责人，选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有 N (1 <= N <= 50000) 间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的湖面。
所有的旅游者，都是一批批地来到旅馆的服务台，希望能订到 Di (1 <= Di <= N) 间连续的房间。服务台的接待工作也很简单：如果存在 r 满足编号为 r..r+Di-1 的房间均空着，他就将这一批顾客安排到这些房间入住；如果没有满足条件的 r，他会道歉说没有足够的空房间，请顾客们另找一家宾馆。如果有多个满足条件的 r，服务员会选择其中最小的一个。
旅馆中的退房服务也是批量进行的。每一个退房请求由 2 个数字 Xi、Di 描述，表示编号为 Xi..Xi+Di-1 (1 <= Xi <= N-Di+1) 房间中的客人全部离开。退房前，请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。
你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共需要处理 M (1 <=M <=50000) 个按输入次序到来的住店或退房的请求。第一个请求到来前，旅店中所有房间都是空闲的。
题目分析：
区间线段树，维护一个区间从左边开始数最多连续空房数量和从右边开始数的，那么对于一个区间 [x,y]，将其分为 [x,mid] 和 [mid+1,y] 后，最多连续空房数是左边区间最多连续空房数，右边区间最多连续空房数，跨越两个子区间的最多连续空房数的最大值。
这样就 easy 了，退房很简单，入住的花只要左区间房间苟去左区间找，否则看跨越两个子区间的区间，否则看右区间这样的顺序寻找即可。注意寻找的时候如果找到了一个 s==t（意思看代码），要 return 否则会 RE
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=50005;
int num[N<<2],ls[N<<2],rs[N<<2],laz[N<<2];
//1:empty 2:you ren
int n,m;
void pd(int i,int s,int t){
    int l=i<<1,r=(i<<1)|1,mid=(s+t)>>1;
    laz[l]=laz[r]=laz[i];
    if(laz[i]==1){
        num[l]=ls[l]=rs[l]=mid-s+1;
        num[r]=ls[r]=rs[r]=t-mid;
    }
    else {
        num[l]=ls[l]=rs[l]=0;
        num[r]=ls[r]=rs[r]=0;
    }
    laz[i]=0;
}
void up(int i,int s,int t){
    int l=i<<1,r=(i<<1)|1,mid=(s+t)>>1;
    num[i]=max(num[l],num[r]);
    if(rs[l]+ls[r]>num[i])num[i]=rs[l]+ls[r];
    ls[i]=ls[l];
    if(ls[l]==mid-s+1)ls[i]+=ls[r];
    rs[i]=rs[r];
    if(rs[r]==t-mid)rs[i]+=rs[l];
}
int query(int x,int s,int t,int i){
    if(s==t)return s;//注意别漏了这句
    int mid=(s+t)>>1;
    if(laz[i])pd(i,s,t);
    if(num[i<<1]>=x)return query(x,s,mid,i<<1);
    if(rs[i<<1]+ls[(i<<1)|1]>=x)return mid-rs[i<<1]+1;
    return query(x,mid+1,t,(i<<1)|1);
}
void chan(int l,int r,int s,int t,int i,int z){
    if(l<=s&&t<=r){
        laz[i]=z+1;
        if(!z)num[i]=ls[i]=rs[i]=t-s+1;
        else num[i]=ls[i]=rs[i]=0;
        return;
    }
    if(laz[i])pd(i,s,t);
    int mid=(s+t)>>1;
    if(l<=mid)chan(l,r,s,mid,i<<1,z);
    if(mid+1<=r)chan(l,r,mid+1,t,(i<<1)|1,z);
    up(i,s,t);
}
void build(int s,int t,int i){
    if(s==t){ls[i]=rs[i]=num[i]=1;return;}
    int mid=(s+t)>>1;
    build(s,mid,i<<1),build(mid+1,t,(i<<1)|1);
    up(i,s,t);
}
int main()
{
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);
    int i,x,y,bj,re;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(i=1;i<=m;++i){
        scanf("%d",&bj);
        if(bj==1){
            scanf("%d",&x);
            if(num[1]<x)printf("0n");
            else {
                re=query(x,1,n,1);printf("%dn",re);
                chan(re,re+x-1,1,n,1,1);
            }
        }
        else {
            scanf("%d%d",&x,&y);
            chan(x,x+y-1,1,n,1,0);
        }
    }
    return 0;
}

T4

期望得分：50 实际得分：52
题目描述：
Mountain Amusement 公园新添了一台过山车，模拟轨道由 n 个首尾相连的铁轨构成，第一根铁轨的首端的高度为 0。操作员 Byteman 可以随意调整一些铁轨两端的高度差，而其他铁轨两端的高度差不受影响。每当一根铁轨的高度差被调整后，与它相连的下一根铁轨将相应地被抬高或被降低，而其首端与前一根铁轨的尾端高度差仍然为 0。下一页的图示说明了轨道调整的两个例子。
过山车的每次运行都被赋予能达到高度 h 的能量。这就是说，只要高度不超过 h，过山车就将一直前进，直至终点。给出每天过山车运行和轨道调整的记录，计算出每次过山车在停止前通过的轨道的长度。
在内部，模拟器将轨道表示为 n 段铁轨两端高度差的序列。第 i 个数 di 表示第 i 段铁轨两端的高度差 (单位为厘米)。假定在通过第 i−1 段铁轨后的过山车的高度为 h 厘米，在经过第 i 段铁轨后，其高度将达到 h+di 厘米。
开始时所有的铁轨都是水平的，也就是说，对所有的 i, di = 0。过山车的运行和轨道的调整在一天之中交错进行。每次轨道调整由三个数描述，a、b、和 D。被调整的区间包含
从 a 到 b 的所有铁轨（a 和 b 都包括在内）。区间内的每根铁轨两端的高度差都被设置为 D。这也就是说，对于所有的 a<= i<= b ， di = D 。
每一次过山车的运行用一个数 h 来表示过山车所能到达的最大高度。
任务
写出程序
从标准输入上读入交错输入的轨道调整和过山车运行的数据。
对过山车的每一次运行，计算它所能通过的铁轨的数量。
将结果写到标准输出上。
数据范围：
输入第一列包含一个正整数 n，1 <= n <=1,000,000,000，表示过山车的运行次数。以
下各行交错包含着轨道调整和过山车运行的数据，以及结束符。每一行可以是下列情况之一：
– 轨道的调整：单个字符 “I” 以及整数 a, b 和 D，及由单个空格符分隔 (1 <= a <= b
<= n, −1,000,000,000 <= D <= 1,000,000,000)。
– 过山车的运行：单个字符 “Q” 和整数 h (0 <= h <= 1,000,000,000) 由单个空格
符分隔。
– 单个字符 “E”：结束符。说明输入数据结束。
你可以假定在任何时候，任何点的高度都在 [0, 1,000,000,000] 厘米之内。输入数据不超
过 100,000 行。
50% 的数据保证 1 <=n <=20,000，以及输入数据不超过 1,000 行。

题目分析：
一开始虽然想到了线段树解法，但奈何离散使我面目全非，最后只打了暴力……
那么这个里面的花，离散要怎么搞呢？
离开了代码根本不好讲，大约是首先将所有修改区间弄成左闭右开区间（为什么之后就知道了），然后离散要用到的区间节点，离散数组 a，线段树中 [s,t] 表示 [a[s],a[t]-1] 这一段（明白为什么是左闭右开了吧），这样线段树左右子树应该是 [s,mid] 和 [mid,t] 而不是我们常用的 [s,mid] 和 [mid+1,t]。
然后线段树维护的是表明每一个铁轨左右高度差的数组，需要维护：sum 区间和，ma 区间高度最大值。注意，如果我们只考虑 [s,t] 区间，我们可以运用物理里常说的” 转换参考系 “的技巧，即把最左端的铁轨的左端看作高度为 0. 这样的花在 pushup 这个 ma 的时候应该是：ma[i]=max(ma[左子树],sum[左子树]+ma[右子树]), 以此类推。
然后查询时，如果左边区间的 ma 要比 h 高的花，车在左边区间就停下来了，就去左边区间找，否则去右边找，并根据参考系的调整对一些参数进行相应的调整（具体看代码）
这题在实现上有很多值得注意的细节，都在代码里打出注释表明了。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define LL long long
const int N=100005,inf=-(1e9+1);
int a[N<<1],cn=1;
int x[N],y[N],z[N];
LL ma[N<<3],sum[N<<3],laz[N<<3];
int n,m;
void make(int i,LL l,LL h){
    sum[i]=h*l,laz[i]=h;
    if(h<0)ma[i]=h;//注意这里
    else ma[i]=sum[i];
}
void pd(int i,int s,int t){
    int l=i<<1,r=(i<<1)|1,mid=(s+t)>>1;
    make(l,a[mid]-a[s],laz[i]),make(r,a[t]-a[mid],laz[i]);
    laz[i]=inf;
}
void chan(int l,int r,int s,int t,int i,int zz){
    if(l<=a[s]&&a[t]<=r){make(i,a[t]-a[s],zz);return;}
    int mid=(s+t)>>1;
    if(laz[i]!=inf)pd(i,s,t);
    if(l<a[mid])chan(l,r,s,mid,i<<1,zz);
    if(r>a[mid])chan(l,r,mid,t,(i<<1)|1,zz);
    sum[i]=sum[i<<1]+sum[(i<<1)|1];
    ma[i]=max(ma[i<<1],sum[i<<1]+ma[(i<<1)|1]);
}
void query(int h,int s,int t,int i){
    if(s==t-1){
        int re=a[t];
        if(laz[i]>0)re=a[s]+h/laz[i];//laz[i] 就是 a[s]~a[t]-1 中铁轨高度
        //不能写 laz[i]!=inf, 否则等着除以 0 来 RE 吧 
        if(re-1<=a[n]-1)printf("%d\n",re-1);//注意特判，有可能延伸出了 a[n]-1 啊 
        else printf("%d\n",a[n]-1);
        return;
    }
    int mid=(s+t)>>1;
    if(laz[i]!=inf)pd(i,s,t);
    if(h<ma[i<<1])query(h,s,mid,i<<1);
    else query(h-sum[i<<1],mid,t,(i<<1)|1);
}
int main(){
    freopen("mou.in","r",stdin);
    freopen("mou.out","w",stdout);
    char ch[5];int i;
    scanf("%d",&a[1]);++a[1];//s~t: 从 a[s] 到 a[t]-1.
    while(1){
        scanf("%s",ch);
        if(ch[0]=='E')break;
        ++m;
        if(ch[0]=='I'){
            scanf("%d%d%d",&x[m],&y[m],&z[m]);//改成左闭右开区间
            if(y[m]<x[m])swap(x[m],y[m]);
            ++y[m];a[++cn]=x[m],a[++cn]=y[m];
        }
        else scanf("%d",&z[m]);
    }
    sort(a+1,a+1+cn);
    n=1;for(i=2;i<=cn;++i)if(a[i]!=a[n])a[++n]=a[i];
    for(i=1;i<(N<<3);++i)laz[i]=inf;
    for(i=1;i<=m;++i){
        if(x[i])chan(x[i],y[i],1,n,1,z[i]);
        else query(z[i],1,n,1);
    }
    return 0;
}