T1大意：给一个序列，每次修改一个数，求每次修改后的众数
sol：数据结构sb题，离散完之后套一个权值线段树就过了
#include <map> #include <cstdio> #include <algorithm> using namespace std; const int N=100005,B=10000005; int n,m,a[N],b[N],out[N]; map<int,int>mp; struct stetree{int l,r,ma,oo;}Tree[N<<2]; #define c1 x<<1 #define c2 x<<1|1 inline void Up(int x){if(Tree[c1].ma>Tree[c2].ma||(Tree[c1].ma==Tree[c2].ma&&Tree[c1].oo<Tree[c2].oo)){Tree[x].ma=Tree[c1].ma,Tree[x].oo=Tree[c1].oo;}else {Tree[x].ma=Tree[c2].ma,Tree[x].oo=Tree[c2].oo;}} inline void build(int l,int r,int x){Tree[x].l=l; Tree[x].r=r; if(l==r){Tree[x].ma=0;Tree[x].oo=l;return;} int mid=(l+r)>>1; build(l,mid,c1); build(mid+1,r,c2); Up(x);} inline void ins(int x,int po,int v){if(Tree[x].l==Tree[x].r){Tree[x].ma+=v;return;} int mid=(Tree[x].l+Tree[x].r)>>1; if(po<=mid)ins(c1,po,v); else ins(c2,po,v); Up(x);} inline int que(int x){if(Tree[x].l==Tree[x].r)return Tree[x].oo; int mid=(Tree[x].l+Tree[x].r)>>1; if(Tree[c1].ma>Tree[c2].ma||(Tree[c1].ma==Tree[c2].ma&&Tree[c1].oo<Tree[c2].oo))return que(c1);else return que(c2);} int main() { int i,ma=0,x,y,re=0,tot=0; scanf("%d%d",&n,&m); for(i=1; i<=n; i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); mp[b[1]]=++tot; out[tot]=b[1]; for(i=2;i<=n;i++)if(b[i]==b[i-1])continue;else mp[b[i]]=++tot,out[tot]=b[i]; build(1,n,1); for(i=1; i<=n; i++)ins(1,mp[a[i]],1); while(m--) { scanf("%d%d",&x,&y); ins(1,mp[a[x]],-1); if(!mp[y])mp[y]=++tot,out[tot]=y; ins(1,mp[y],1); a[x]=y; printf("%d ",out[que(1)]); } }
T2大意：给出一个k维的空间，在空间中有n个点，求任意两个点的最大曼哈顿距离
sol：因为abs比较难处理，所以拆开绝对值:考虑直接拆开原来如果是abs（x1-x2），拆成x1-x2,难免会使得x1<x2的情况下无法得到答案，于是暴力枚举每个维度的正负，2^k次一定可以枚举到。
#include <cstdio> #include <algorithm> using namespace std; #define int long long const int N=200005; int n,d,re=0,w[6]; int pp[]={-1,1}; struct Pot{int x[6];}a[N]; inline void solve(int zt) { int i,j,tmp=0,mi=0x7ffffff,ma=-0x7ffffff; for(i=1;i<=d;i++)w[i]=(bool)(zt&(1<<(i-1))); for(i=1;i<=n;i++) { tmp=0; for(j=1;j<=d;j++)tmp+=pp[w[j]]*a[i].x[j]; ma=max(ma,tmp); mi=min(mi,tmp); }re=max(re,ma-mi); } signed main() { int i,j; scanf("%lld%lld",&n,&d); for(i=1;i<=n;i++) { for(j=1;j<=d;j++)scanf("%lld",&a[i].x[j]); }for(i=0;i<(1<<d);i++)solve(i); printf("%lld ",re); }
T3：这大概是到结论题：用前3个往后推，用后3个往前推。
#include <cstdio> #include <algorithm> using namespace std; const int N=1000005; int n,s[N][3]; char ss[N]; inline bool jud(int l,int r) { int a=s[r][0]-s[l-1][0],b=s[r][1]-s[l-1][1],c=s[r][2]-s[l-1][2],bo=0; bo+=(bool)(a)+(bool)(b)+(bool)(c); if(bo==1)return 1; if(a!=b&&a!=c&&b!=c)return 1;return 0; } int main() { int i,j,re=1,bo=0; scanf("%d",&n); scanf("%s",ss+1); s[0][0]=s[0][1]=s[0][2]=0; for(i=1;i<=n;i++)if(ss[i]!='B'){bo=1;break;} if(!bo)return printf("%d ",n),0; for(i=1;i<=n;i++) { s[i][0]=s[i-1][0]; s[i][1]=s[i-1][1]; s[i][2]=s[i-1][2]; switch(ss[i]){case 'C':{s[i][0]++;break;} case 'B':{s[i][1]++;break;} case'S':{s[i][2]++;break;}} } for(i=1;i<=n;i++)if(jud(1,i))re=max(re,i); for(i=2;i<=n;i++)if(jud(2,i))re=max(re,i-1); for(i=3;i<=n;i++)if(jud(3,i))re=max(re,i-2); for(i=n;i>=1;i--)if(jud(i,n))re=max(re,n-i+1); for(i=n-1;i>=1;i--)if(jud(i,n-1))re=max(re,n-i); for(i=n-2;i>=1;i--)if(jud(i,n-2))re=max(re,n-i-1); printf("%d ",re); }