A. 青蛙跳

根号分治去解决

#define M 100005
using namespace std;
int A[M],sum[340][M];
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
    int S=sqrt(n);
	for(int i=n;i>=1;i--)
		for(int j=1;j<=S;j++)
			sum[j][i]=sum[j][i+j]+A[i];		
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		if(b<=S){
			printf("%d\n",sum[b][a]);
		}else{
			int res=0;
			for(int j=a;j<=n;j+=b)
				res+=A[j];
			printf("%d\n",res);
		}
	}
	return 0;
}

B. 微信运动1

依然是根号分治

const int N=2e5+10;
vector<int> e[N];
vector<int> Big[N];
bool st[N];
int d[N];
int n,m,q;
int a[N];
int ans[N];

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	
	cin>>n>>m>>q;
	int B=500;
	for(int i=1,a,b;i<=m;i++)
	{
		cin>>a>>b;
		e[a].push_back(b),e[b].push_back(a);
		d[a]++,d[b]++;
	}	
	
	for(int i=1;i<=n;i++) 
	{
		if(d[i]<=B) continue;
		st[i]=true;
		for(auto v:e[i])
		{
			Big[v].push_back(i);
		}
	}
	
	while(q--)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,w;
			cin>>x>>w;
			a[x]+=w;
			for(auto v:Big[x]) ans[v]=max(ans[v],a[x]);
		}
		else
		{
			int x;
			cin>>x;
			if(!st[x])
			{
				int res=0;
				res=max(res,a[x]);
				for(auto v:e[x]) res=max(res,a[v]);
				cout<<res<<"\n";
			}
			else cout<<max(a[x],ans[x])<<"\n";
		}
	}
	
	return 0;
}

C. 弹飞绵羊

还是一个根号分治，根号预处理，根号查询

const int N=200005,B=450;
int a[N];
int out[N], nxt[N];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d",&a[i]);
	for (int i = n - 1; i >= 0; i--) {
		if (i + a[i] >= n || i / B < (i + a[i]) / B) {
			out[i] = 1;
			nxt[i] = i + a[i];
		} else {
			out[i] = out[i + a[i]] + 1;
			nxt[i] = nxt[i + a[i]];
		}
	}
	int m;
	cin >> m;
	while (m--) {
		int op, x, y;
		scanf("%d%d",&op, &x);
		if (op == 1) {
			int ans = 0;
			for (; x < n; x = nxt[x])
				ans += out[x];
			cout << ans << "\n";
		} else {
			scanf("%d",&a[x]);
			y = x / B;
			for (int i = x; i >= y * B; i--) {
				if (i + a[i] >= n || i / B < (i + a[i]) / B) {
					out[i] = 1;
					nxt[i] = i + a[i];
				} else {
					out[i] = out[i + a[i]] + 1;
					nxt[i] = nxt[i + a[i]];
				}
			}
		}
	}
}

D. 区间和升级版

为了根号分治而根号分治

#define int long long
int n,m,x,y,s,a[100009],b[321];
char c[12];
void update(int p,int x){b[p/s]+=x-a[p],a[p]=x;}
void sum(int l,int r,int &res){for(int i=l;i<=r;i++)res+=a[i];}
void all(int l,int r,int &res){for(int i=l;i<=r;i++)res+=b[i];}
int query(int l,int r){
	int L=l/s,R=r/s,res=0;
	if(L==R)sum(l,r,res);
	else sum(l,(L+1)*s-1,res),sum(R*s,r,res),all(L+1,R-1,res);
	return res;
} 
signed main(){
	scanf("%d %d",&n,&m);s=sqrt(n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i/s]+=a[i];
	while(m--){
		scanf("%s %d %d",c,&x,&y);
		if(c[0]=='C')update(x,y);
		else printf("%d\n",query(x,y));
	}
}

E. 最远相同数

挺难的

const int N = 5e5+5;
const int M = sqrt(N+0.5)+5;
 
vector<ll>ve[M];
ll atag[M],v[N];
int blo,bl[N],n;
 
void reset(int k)
{
    ve[k].clear();
    for (int i=blo*(k-1)+1;i<=min(blo*k,n);i++)
        ve[k].pb(v[i]);
    sort(ve[k].begin(),ve[k].end());
}
 
void update(int l,int r,ll x)
{
    for (int i=l;i<=min(r,blo*bl[l]);i++)
        v[i] += x;
    reset(bl[l]);
    if (bl[l]!=bl[r]){
        for (int i=blo*(bl[r]-1)+1;i<=r;i++)
            v[i] += x;
        reset(bl[r]);
    }
    for (int i=bl[l]+1;i<=bl[r]-1;i++)
        atag[i] += x;
}
 
int query(ll x)
{
    int ansl,ansr;
    int pos = -1;
    for (int i=1;i<=bl[n];i++)
        if ( binary_search(ve[i].begin(),ve[i].end(),x-atag[i]) ){
            pos = i;
            break;
        }
 
    if (pos==-1) return -1;
 
    for (int i=blo*(pos-1)+1;i<=min(blo*pos,n);i++)
        if (v[i]+atag[pos]==x) {
            ansl = i;
            break;
        }
    for (int i=bl[n];i>=1;i--)
        if ( binary_search(ve[i].begin(),ve[i].end(),x-atag[i]) ) {
            pos = i;
            break;
        }
    for (int i=min(pos*blo,n);i>=blo*(pos-1)+1;i--)
        if (v[i]+atag[pos]==x) {
            ansr = i;
            break;
        }
 
    return ansr-ansl;
}
 
int main()
{
    int t,l,r,op;
    ll x;
    while (~scanf("%d %d",&n,&t)){
        blo = sqrt(n+0.5);
        for (int i=1;i<=M;i++) ve[i].clear();
        memset(atag,0,sizeof atag);
        for (int i=1;i<=n;i++){
            scanf("%I64d",v+i);
            bl[i] = (i-1)/blo+1;
            ve[bl[i]].pb(v[i]);
        }
        for (int i=1;i<=bl[n];i++) sort(ve[i].begin(),ve[i].end());
        while (t--){
            scanf("%d",&op);
            if (op==1) scanf("%d %d %I64d",&l,&r,&x),update(l,r,x);
            else scanf("%I64d",&x),printf("%d\n",query(x));
        }
    }
}