B
题意是你的手机屏幕最多容纳K个朋友的消息在这里，没秒会有一个人发一条短信过来，当第k+1个人发短信过来，你的屏幕为了显示它同时又由于最多只能容纳k个，就会相queue容器一样把先进来的给弹出屏幕显示
思路：map容器模拟
#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
#define LL long long
const int N=4e5+5;
const int mod=1e9+7;
int n,m,k;
int a[N],b[N];
bool vis[N];
map<int,int>mp;
int main(){
cin>>n>>k;
int x=0;
for(int i=1;i<=n;i++){
scanf("%d",a+i);
if(mp.find(a[i])==mp.end())
mp[a[i]]=++x;
}
int len=0,la=0;
for(int i=1;i<=n;i++){
int x=mp[a[i]];
if(vis[x])
continue;
if(len==k)
vis[mp[b[la-len+1]]]=false,len--;
len++;
b[++la]=a[i];
vis[x]=true;
}
printf("%d
",len);
for(int i=la;i>=la-len+1;i--)
printf("%d ",b[i]);
return 0;
}
C
题意就是像以爷爷手机玩过的小游戏，一个水管有—这种，还有|_这种，他们可以旋转变化，现在你有2*n的格子，每个格子都有一个水管，问你能不能通过旋转这些水管使得这些水流可以从左上角到右下角
思路：
：假设水是从第k列第j行流向第k + 1列, 那么第k+1列肯定是用第j行的管子接水 , 如果第k+1列第j行的管子类型为1 , 那么水将直接流向第k+2列 ; 如果第k+1列第j行的管子类型为2 , 那么水只能传给 j 的上一行或者下一行 , 然后再传向第k+2列 , 因为每行每列的管子类型已经确定了, 所以水的流向也就是固定的了。而水能从当前列流向下一列的条件只有几个 ：
①接收水的管子类型为 1 ，所在行为 j 直接流向下一列的第 j 行
②接收水的管子类型为 2 ， 则如果 j ^ 1 行管子的类型也为 2 ， 则流向下一列的第 j ^ 1行
剩下情况水皆不能流通（水不能倒流） ， 所以直接dfs跑一遍就可以了
60 bool dfs(int i, int j)
61 {
62 if(i == n && j == 1)
63 return 1;
64 if(i == n) return 0;
65 if(s[0][i] == '1' && s[1][i] == '2')
66 {
67 if(j == 0) return dfs(i + 1 , 0);///当水从在第一行过来同时是一号水管，第二行是2号水管，那么dfs，如果水从第二行过来碰到二号水管就肯定没办法了
68 else return 0;
69 }
70 if(s[0][i] == '2' && s[1][i] == '1')///同理和上面一样
71 {
72 if(j == 1) return dfs(i + 1 , 1);
73 else return 0;
74 }
75 if(s[0][i] == '1' && s[1][i] == '1')///都是一号水管，哪里过来就的dfs的j就是水流过来的行位置
76 {
77 return dfs(i + 1 , j);
78 }
79 if(s[0][i] == '2' && s[1][i] == '2')///这里如果都是2号水管，那么水从上面来就得下面流出去，从下面来就得上面溜出去
80 {
81 return dfs(i + 1 , j ^ 1);
82 }
83 }
D
题意：给你一个字符串 ， 有q个操作：
①、 将 pos 位置的字符改为 c
②、查询 L~ R 区间不同字符的个数
分析：
挺水的一题。因为全是小写字符 , 所以我们可以对每个单独字符开个线段树, 那么一共就开了26个线段树 ,然后预处理：将母串中第 i 个位置的字符对应的线段树的第 i 个区间的值 + 1。
那么当操作为 ① 的时候我们只要将母串pos位置的字符对应线段树的pos区间值 -1 , 然后c字符对应线段树的pos区间 +1
当操作为 ②的时候我们只要判断每个字符是否有出现在L ~ R区间 , 即遍历 26 颗线段树 L ~ R 的区间和是否为 0 .若不为 0 , ans++ , 遍历完后输出ans即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int a[N],ans[30];
int tree[4*N][26];
void build(int l,int r,int rt){
if(l==r){tree[rt][a[l]]++;return ;}
int mid=(l+r)/2;
build(l,mid,rt*2);
build(mid+1,r,rt*2+1);
for(int i = 0;i < 26;++i)tree[rt][i]=tree[rt*2][i]+tree[rt*2+1][i];
}
void f5(int l,int r,int rt,int x,int p,int f){
if(l==r){tree[rt][p]--;tree[rt][f]++;return ;}
int mid=(l+r)>>1;
if(x<=mid)f5(l,mid,rt<<1,x,p,f);
else f5(mid+1,r,rt<<1|1,x,p,f);
for(int i = 0;i < 26;++i)tree[rt][i]=tree[rt<<1][i]+tree[rt<<1|1][i];
}
void query(int l,int r,int rt,int ll,int rr){
if(r<=rr&&l>=ll){
for(int i = 0;i < 26;++i)ans[i]+=tree[rt][i]; return ;
}
int mid=(l+r)>>1;
if(ll<=mid)query(l,mid,rt<<1,ll,rr);
if(rr>mid)query(mid+1,r,rt<<1|1,ll,rr);
}
int main()
{
ios::sync_with_stdio(0);
string s;cin>>s;int n = s.size();
for(int i = 0;i < n;++i)a[i+1]=s[i]-'a';
build(1,n,1);
int m;cin>>m;
while(m--){
int flag,x,l,r;char c;cin>>flag;
if(flag==1){
cin>>x>>c;
f5(1,n,1,x,s[x-1]-'a',c-'a');
s[x-1]=c;
}
else{
cin>>l>>r;memset(ans,0,sizeof(ans));
query(1,n,1,l,r);
int tot=0;
for(int i = 0;i < 26;++i)if(ans[i])tot++;
cout<<tot<<endl;
}
}
return 0;
}