两次考试，两次惊魂
第一次尽管由于T2的SB操作丢了20分，但勉强从17分干到了15发，卡住了第一机房线
当我刚放松一些时，教练传来消息：下次考试后分机房
WTF？！？！？好吧继续考
T130min切掉（由于不会打暴力并没有对拍），T250pts暴力打完，又30min思考正解无果后还有1h，转战T3
T3明显的数位DP，然而由于状态定义错误调不出来，最后用3min打了个暴力扔上去
然后T3爆零了，原因是我把一个变量充定义然后它死循环了
当我看考完看着rank19的排名时，刚感觉要完戏，结果总榜一出，还是rank15？！
然后我就苟在了第一机房
怎么说呢，这段时间考试总是不在状态，尽管后期有了调整然而并不能挽回之前的失误
继续努力吧
0813：
T1：周
爆搜，不解释
T2：任
emmm.....这题我的思路和其他人不太一样，大概说一下
假设我们是一行一行来统计贡献，上一行的贡献为x，这一行的贡献是为多少
我们先处理出来每一行块数的前缀和sum，以及每一行和上一行连边数的前缀和link_x
那么显然我们这一行的贡献为sum-link_x，这个东西可以用二维前缀和维护，可以O(1)查询
然而这样会出问题，因为我们左边界的前缀和可能是错误的
我们可以处理出每列和左边相连的前缀和link_y来解决这个问题
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mx[4]={1,-1,0,0},my[4]={0,0,1,-1};
int n,m,q,ans,now,xxx,yyy,xx,yy,sol[2002][2002],slm[2002][2002],sim[2002][2002];
char s[2010][2010];
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sol[i][j]=sol[i][j-1]+sol[i-1][j]-sol[i-1][j-1];
if(s[i][j-1]!='1'&&s[i][j]=='1') sol[i][j]++;
slm[i][j]=slm[i][j-1]+slm[i-1][j]-slm[i-1][j-1];
if(s[i][j]=='1'&&s[i-1][j]=='1') slm[i][j]++;
sim[i][j]=sim[i-1][j];
if(s[i][j]==s[i][j-1]&&s[i][j]=='1') sim[i][j]++;
}
}
while(scanf("%d%d%d%d",&xxx,&yyy,&xx,&yy)==4){
ans=sol[xx][yy]-sol[xxx-1][yy]-sol[xx][yyy-1]+sol[xxx-1][yyy-1]+sim[xx][yyy]-sim[xxx-1][yyy];
if(xx-xxx>=1) ans-=slm[xx][yy]-slm[xxx][yy]-slm[xx][yyy-1]+slm[xxx][yyy-1];
printf("%d
",ans);
}
return 0;
}
T3：飞
首先，我们仔细观察鬼畜值的定义，会惊奇的发现他让求的就是C(x,2)，即两两相交的个数
又由于y单调递增，问题进一步转化为求逆序对数
然而这题卡内存，我们需要一些特殊的处理方法
我们发现X是由多段等差数列组成的
考虑等差数列中两项Xi和Xi+1的关联，发现Xi+1的答案就是Xi的答案-之前循环次数
因为之前每个数列必有一个数和Xi构成逆序对而和Xi+1构不成逆序对
对每个数列第一项特殊处理就好了
第一个不完整的数列需要加特判
#include<bits/stdc++.h>
#define ll long long
#define cri const register int
#define re register
using namespace std;
ll c[100010],a;
inline void add(cri x){
for(int i=x;i<=a;i+=i&-i) c[i]++;
}
inline ll get(cri x){
ll ans=0;
for(int i=x;i>=1;i-=i&-i) ans+=c[i];
return ans;
}
int main(){
ll n,X,mod,x,lst,ans=0,num=0,i,lans;
scanf("%lld%lld%lld%lld",&n,&X,&a,&mod);
if(X<a) add(X+1);
lst=X;
x=(X+a)%mod;
for(i=2;i<=n&&x>=a;i++){
lst=x;
x+=a;
if(x>=mod) x-=mod;
}
for(i;i<=n;i++){
if(x<a) ans+=(lst=i-1-(get(x+1))),num++,add(x+1);
else ans+=(lst=lst-num+(x<X));
x+=a;
if(x>=mod) x-=mod;
}
printf("%lld",ans);
}
未完待续咕了