# T1

pyh 大佬说，假如某一元素在序列里出现了若干次，位置为 a1,a2…an，我们就在平面上建立点 (a1,a2),(a2,a3),(a3,a4)….[我的思路是离散出现的数字]

#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);}//树状数组
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){
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

C(A, B, C) 将第 A 段到第 B 段全部涂成颜色 C
P(A, B) 计算第 A 段到第 B 段间不同的颜色数 (包含 A 和 B 段)

#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

XXX 最近的旅游计划，是到 XXXX 湖畔，享受那里的湖光山色，以及明媚的阳光。你作为整个旅游的策划者和负责人，选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有 N (1 <= N <= 50000) 间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的湖面。

#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

Mountain Amusement 公园新添了一台过山车，模拟轨道由 n 个首尾相连的铁轨构成，第一根铁轨的首端的高度为 0。操作员 Byteman 可以随意调整一些铁轨两端的高度差，而其他铁轨两端的高度差不受影响。每当一根铁轨的高度差被调整后，与它相连的下一根铁轨将相应地被抬高或被降低，而其首端与前一根铁轨的尾端高度差仍然为 0。下一页的图示说明了轨道调整的两个例子。

– 轨道的调整：单个字符 “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”：结束符。说明输入数据结束。

50% 的数据保证 1 <=n <=20,000，以及输入数据不超过 1,000 行。

#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;
}