深切理解湖南人民的苦难

可是泥萌一个个都170什么意思啊QAQ

T1. 序列

传送门： http://www.lydsy.com/JudgeOnline/problem.php?id=4540

标算是莫队辣

为什么有这么多的分块题。。这次T3又是莫队QAQ。。

加上上次的T1。简直分块训练营（大雾）

湖南真是个神奇的地方

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
#define NN 100010
#define LL long long
using namespace std;
struct Query
{
	int l,r,id;
}q[NN];
int st[NN],a[NN],l[NN],r[NN],f[NN][20],n,m,top=0,block,Log[NN];
LL ans[NN],now,ld[NN],rd[NN];
bool cmp1(Query xx,Query yy)
{
	if (xx.l/block==yy.l/block) return xx.r<yy.r;
	else return xx.l/block<yy.l/block;
}
int read()
{
	int xx; bool f=0; char CH;
	for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
	for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
	return xx;
}
int Q(int x,int y)
{
	int tmpp=(int)log2(y-x+1);
	if (a[f[x][tmpp]]<a[f[y-(1<<tmpp)+1][tmpp]]) return f[x][tmpp];
	else return f[y-(1<<tmpp)+1][tmpp];
}
void L_(int x,int y,LL t)
{
	int tmp=Q(x,y);
	now+=t*a[tmp]*(y-tmp+1)+t*(rd[x]-rd[tmp]);
}
void R_(int x,int y,LL t)
{
	int tmp=Q(x,y);
	now+=t*a[tmp]*(tmp-x+1)+t*(ld[y]-ld[tmp]);
}
void pre()
{
	for (int i=1;i<=n;++i)
	{
		while (top && a[st[top]]>a[i]) r[st[top--]]=i;
		if (a[st[top]]==a[i]) l[i]=l[st[top]]; else l[i]=st[top];
		st[++top]=i;
	}
	while (top) r[st[top--]]=n+1;
	for (int i=1;i<=n;++i) ld[i]=ld[l[i]]+1ll*(i-l[i])*a[i];
	for (int i=n;i>=1;--i) rd[i]=rd[r[i]]+1ll*(r[i]-i)*a[i];
	for (int i=1;i<=n;++i) f[i][0]=i;
	for (int i=1;(1<<i)<=n;++i)
		for (int j=1;j<=n-(1<<i)+1;j++)
		{
			if (a[f[j][i-1]]<a[f[j+(1<<(i-1))][i-1]]) f[j][i]=f[j][i-1];
			else f[j][i]=f[j+(1<<(i-1))][i-1];
		}
}
int main()
{
	n=read(), m=read();
	block=(int)sqrt(n);
	for (int i=1;i<=n;++i) a[i]=read();
	pre();
	for (int i=1;i<=m;++i) q[i].l=read(), q[i].r=read(), q[i].id=i;
	sort(q+1,q+1+m,cmp1);
	int x=1,y=1;
	now=a[1];
	for (int i=1;i<=m;++i)
	{
		if (q[i].r>y) while (y!=q[i].r) y++, R_(x,y,1);
		if (q[i].l>x) while (x!=q[i].l) L_(x,y,-1), x++;
		if (q[i].l<x) while (x!=q[i].l) x--, L_(x,y,1);
		if (q[i].r<y) while (y!=q[i].r) R_(x,y,-1), y--;
		ans[q[i].id]=now;
	}
	for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
	return 0;
}

T2. 矿区

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4541

彩蛋：输出k个“1 1”就可以10分走人咯

T3. 大数

传送门：　http://www.lydsy.com/JudgeOnline/problem.php?id=4542

你觉得我考试的时候还真的有时间写么

好吧QAQ（现在年轻人一言不合就写暴力

暴力30分的挣扎

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
char s[1010];
LL mod;
int m,ans,l,r;
LL xx;
int main()
{
	scanf("%lld%s%d",&mod,s,&m);
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&l,&r); l--,r--;
		ans=0;
		for (int j=l;j<=r;++j)
		{
			xx=0ll;
			for (int k=j;k<=r;++k)
			{
				xx=xx*10ll%mod+s[k]-'0';
				if (xx%mod==0) ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

标算是Scarlet大爷的

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rpt(i,l,r) for(int i=l;i<=r;i++)
#define rpd(i,r,l) for(int i=r;i>=l;i--)
#define N 100005
long long P;
char s[N];
int n,m,d,nl,nr;
int dv[N];
long long temp;
long long a[N],dict[N];
int b[N],c[N];
struct query{
    int l,r,x;
}q[N];
inline bool cmp(query a,query b){
    return dv[a.l]==dv[b.l]?a.r<b.r:dv[a.l]<dv[b.l];
}
long long ans_,ans[N];
int main(){
    std::cin>>P;
    scanf("%s",s+1);
    n=strlen(s+1);
       
    if(P==2||P==5){
        rpt(i,1,n) if((s[i]-'0')%P==0) a[i]=i,b[i]=1;
        a[0]=0;rpt(i,1,n) a[i]+=a[i-1];
        b[0]=0;rpt(i,1,n) b[i]+=b[i-1];
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&nl,&nr);
            printf("%lld\n",a[nr]-a[nl-1]-1LL*(b[nr]-b[nl-1])*(nl-1));
        }
    }
    else{
           
    a[n+1]=0;temp=1;
    rpd(i,n,1) a[i]=((s[i]-'0')*temp+a[i+1])%P,(temp*=10)%=P;
    n++;rpt(i,1,n) dict[i]=a[i];
    std::sort(dict+1,dict+n+1);
    rpt(i,1,n) b[i]=std::lower_bound(dict+1,dict+n+1,a[i])-dict;
       
    scanf("%d",&m);
    rpt(i,1,m) scanf("%d%d",&q[i].l,&q[i].r),q[i].r++,q[i].x=i;
    d=int(sqrt(n));rpt(i,1,n) dv[i]=i/d;
    std::sort(q+1,q+m+1,cmp);
       
    memset(c,0,sizeof(c));
    nl=1;nr=0;ans_=0;
    rpt(i,1,m){
        if(nr<q[i].r){
            rpt(j,nr+1,q[i].r) ans_+=c[b[j]]++;
            nr=q[i].r;
        }
        if(nl>q[i].l){
            rpd(j,nl-1,q[i].l) ans_+=c[b[j]]++;
            nl=q[i].l;
        }
        if(nr>q[i].r){
            rpt(j,q[i].r+1,nr) ans_-=--c[b[j]];
            nr=q[i].r;
        }
        if(nl<q[i].l){
            rpd(j,q[i].l-1,nl) ans_-=--c[b[j]];
            nl=q[i].l;
        }
        ans[q[i].x]=ans_;
    }
    rpt(i,1,m) printf("%lld\n",ans[i]);
       
    }
}