这套月赛题不是特别难
T1：离散化+单调队列，队列里出现数的种类不超过K+1，找最大的num[a[i]]
T2：一眼可以看出BFS+状压DP，还要SPFA预处理出各个块之间的dis
T3：线段树，没什么难度
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
;
int n,K,a[maxn],b[maxn],m,ans,head,tail,q[maxn],vis[maxn],cnt;
int main(){
scanf("%d%d", &n, &K);
; i<=n; i++) scanf("%d", &b[i]),a[i]=b[i];
sort(b+,b++n);
m=unique(b+,b++n)-b-;
; i<=n; i++) a[i]=lower_bound(b+,b++m,a[i])-b;
//for (int i=1; i<=n; i++) printf("%d\n", a[i]);
head=tail=cnt=;
; i<=n; i++){
if (!vis[a[i]]) cnt++;
vis[a[i]]++; q[tail++]=i;
){
vis[a[q[head]]]--; ) cnt--;
head++;
}
ans=max(ans,vis[a[q[tail-]]]);
}
printf("%d\n", ans);
;
}
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
;
]={,,,-};
]={,-,,};
struct node{
int x,y;
node(int _x, int _y):x(_x),y(_y){}
};
<<][],dis[][],id[maxn][maxn],vis[maxn][maxn],cnt,stx[],sty[],N;
char s[maxn][maxn];
bool check(int x, int y){
|| y< || x>n || y>m) ; ;
}
void bfs(int sx, int sy, int num){
queue<node> Q;
Q.push(node(sx,sy)); id[sx][sy]=num;
vis[sx][sy]=;
while (!Q.empty()){
int x=Q.front().x, y=Q.front().y; Q.pop();
; k<; k++){
int tx=x+dx[k], ty=y+dy[k];
if (check(tx,ty) && !vis[tx][ty] && s[tx][ty]=='X'){
vis[tx][ty]=; id[tx][ty]=num;
Q.push(node(tx,ty));
}
}
}
}
void find_land(){
cnt=;
; i<=n; i++)
; j<=m; j++)
if (s[i][j]=='X' && !vis[i][j]){
bfs(i,j,++cnt);
stx[cnt]=i; sty[cnt]=j;
}
// for (int i=1; i<=cnt; i++) printf(" %d %d\n", stx[i], sty[i]);
}
void spfa(int sx, int sy, int num){
queue<node> Q;
int next,cost; memset(d,0x3f,sizeof(d));
memset(dis[num],0x3f,sizeof(dis[num]));
Q.push(node(sx,sy)); d[sx][sy]=; vis[sx][sy]=; dis[num][num]=;
while (!Q.empty()){
int x=Q.front().x, y=Q.front().y; Q.pop();
; k<; k++){
int tx=x+dx[k], ty=y+dy[k];
if (!check(tx,ty) || s[tx][ty]=='.') continue;
cost=(s[tx][ty]=='S');
if (d[tx][ty]>d[x][y]+cost){
d[tx][ty]=d[x][y]+cost;
){
vis[tx][ty]=;
Q.push(node(tx,ty));
}
}
if ((s[tx][ty]=='X') && ((next=id[tx][ty])!=num)) dis[num][next]=min(dis[num][next],d[tx][ty]);
}
vis[x][y]=;
}
}
void dp(){
N=(<<cnt);
memset(f,0x3f,sizeof(f));
; i<=cnt; i++) f[(<<(i-))][i]=;
; s<N; s++){
; i<=cnt; i++) <<(i-)))
; j<=cnt; j++) <<(j-))))
f[s^(<<(j-))][j]=min(f[s^(<<(j-))][j],f[s][i]+dis[i][j]);
}
int ans=0x7fffffff;
; i<=cnt; i++) ans=min(ans,f[N-][i]);
printf("%d\n", ans);
}
int main(){
scanf("%d%d", &n, &m);
; i<=n; i++){
scanf();
}
find_land();
; i<=cnt; i++)
spfa(stx[i],sty[i],i);
dp();
;
}
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
;
struct node{
int l,r,len,lz,lm,rm,mx;
}t[maxn*],now;
int n,m,x,y,ans;
];
void pushup(int x){
t[x].lm=t[x<<].lm;
].lm==t[x<<].len) t[x].lm=t[x<<].len+t[x<<|].lm;
t[x].rm=t[x<<|].rm;
|].rm==t[x<<|].len) t[x].rm=t[x<<|].len+t[x<<].rm;
t[x].mx=max(t[x<<].rm+t[x<<|].lm,max(t[x<<].mx,t[x<<|].mx));
}
void pushdown(int x){
){ //涂色
t[x<<].lz=; t[x<<|].lz=;
t[x<<].lm=t[x<<].rm=t[x<<].mx=;
t[x<<|].lm=t[x<<|].rm=t[x<<|].mx=;
}
){ //不涂色
t[x<<].lz=; t[x<<|].lz=;
t[x<<].lm=t[x<<].rm=t[x<<].mx=t[x<<].len;
t[x<<|].lm=t[x<<|].rm=t[x<<|].mx=t[x<<|].len;
}
t[x].lz=;
}
node query(int x, int p){
int l=t[x].l, r=t[x].r;
pushdown(x);
].mx>=p) ,p);
].rm+t[x<<|].lm>=p){
node ret;
ret.l=t[x<<].r-t[x<<].rm+;
ret.r=ret.l+p-;
return ret;
}|,p);
}
void update(int a, int b, int x, int c){
int l=t[x].l, r=t[x].r;
if (l==a && r==b){
){
t[x].lz=;
t[x].lm=t[x].rm=t[x].mx=;
}
){
t[x].lz=;
t[x].lm=t[x].rm=t[x].mx=t[x].len;
}
return;
}
;
pushdown(x);
,c);
|,c);
,c),update(mid+,b,x<<|,c);
pushup(x);
}
void build(int l, int r, int x){
t[x].l=l; t[x].r=r; t[x].len=r-l+;
if (l==r){
t[x].lz=; t[x].lm=t[x].rm=t[x].mx=;
return;
}
;
build(l,mid,x<<);
build(mid+,r,x<<|);
pushup(x);
}
int main(){
scanf("%d%d", &n, &m);
build(,n,);
//printf("%d\n", t[1].mx);
while (m--){
scanf("%s", opt);
]=='A'){
scanf("%d", &x);
].mx<x) ans++;
else{
now=query(,x);
//printf(" %d %d\n", now.l, now.r);
update(now.l,now.r,,);
}
}else{
scanf("%d%d", &x, &y);
update(x,y,,);
}
}
printf("%d\n", ans);
;
}