题目链接：P6528 「Wdoi-1」完美冻结
题目大意：求 (Large{sum_{l_1leq i leq r_1}sum_{l_2leq j leq r_2}left lfloor frac{sum_{l=min(i,j)}^{max(i,j)} a_l}{k} ight floor})
题解：为了之后的方便，我们通过大量的分类讨论来将整个问题转换为 (Large{sum_{lleq i leq r}sum_{lleq jleq r}left lfloor frac{sum_{l=min(i,j)}^{max(i,j)} a_l}{k}
ight
floor})
我们考虑对 (a) 做前缀和，令其前缀和数组为 (s) ，所以我们就是要求 (left lfloor frac{s_j-s_{i-1}}{k} ight floor) 这个东西，我们考虑令 (c_i=left lfloor frac{s_i}{k} ight floor,d_i=s_imod k)
那么我们就可以把原来的式子给换成这个样子：(c_j-c_{i-1}-[d_j<d_{i-1}])
然后我们发现 (sum_{lleq ileq r}sum_{lleq jleq r}c_j-c_{i-1}) 这种东西是可以 (O(n)) 预处理 (O(1)) 求的。
接下来就只剩下 (sum_{lleq ileq r}sum_{lleq jleq r}[d_j<d_{i-1}]) 了，我们把第 (l-1) 位和第 (r) 位单独拎出来，用主席树求一下，剩下的东西 (lsim r-1) 中的区间逆序对，直接套个板子即可。
时间复杂度 (O(nsqrt{q}+qlog n)) 。
但是我的代码自带大常数 /kk。
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
void read(int &a){
a=0;
char c=getchar();
while(c<'0'||c>'9'){
c=getchar();
}
while(c>='0'&&c<='9'){
a=(a<<1)+(a<<3)+(c^48);
c=getchar();
}
}
typedef long long ll;
const int Maxn=200000;
const int Maxm=2000000;
const int Maxb=300;
const int Mod=998244353;
const int inv_2=(Mod+1)>>1;
int n,Q,k,m;
int a[Maxn+5];
ll sum[Maxn+5];
int c[Maxn+5],d[Maxn+5];
int _d[Maxn+5],d_len;
int ans[Maxn+5];
int s_ak[Maxn+5];
int s_c_0[Maxn+5],s_c_1[Maxn+5],s_c_2[Maxn+5];
struct Operation{
int pos,l,r;
int op,id;
Operation(int _pos=0,int _l=0,int _r=0,int _op=0,int _id=0){
pos=_pos;
l=_l;
r=_r;
op=_op;
id=_id;
}
inline friend bool operator <(Operation a,Operation b){
return a.pos<b.pos;
}
}qu[Maxm*3+5];
namespace Block{
int block;
int sum_b[Maxn+5];
int sum_l[Maxn+5];
inline void add(int x,int a){
int num=(x-1)/block+1;
for(int i=num;i<=(d_len-1)/block+1;++i){
sum_b[i]+=a;
}
for(int i=x;i<=min(num*block,d_len);++i){
sum_l[i]+=a;
}
}
inline int query(int l,int r){
if(l>r){
return 0;
}
int bel_l,bel_r;
bel_l=(l-1)/block+1,bel_r=(r-1)/block+1;
if(bel_l==bel_r){
if(l==(bel_l-1)*block+1){
return sum_l[r];
}
return sum_l[r]-sum_l[l-1];
}
int ans=sum_b[bel_r-1]-sum_b[bel_l-1];
if(l!=(bel_l-1)*block+1){
ans-=sum_l[l-1];
}
ans+=sum_l[r];
return ans;
}
}
int qu_len;
int block;
struct Query{
int l,r;
int id;
inline friend bool operator <(Query a,Query b){
if((a.l-1)/block==(b.l-1)/block){
if(((a.l-1)/block)&1){
return a.r>b.r;
}
return a.r<b.r;
}
return a.l<b.l;
}
}q[Maxm+5];
int q_flag[Maxm+5],q_id[Maxm+5];
int g[Maxn+5],h[Maxn+5];
ll sum_g[Maxn+5],sum_h[Maxn+5];
ll answer[Maxm+5];
namespace BIT{
int f[Maxn+5];
inline void add(int x,int a){
for(int i=x;i<=d_len;i+=(i&(-i))){
f[i]+=a;
}
}
inline int query(int x){
int ans=0;
for(int i=x;i>0;i-=(i&(-i))){
ans+=f[i];
}
return ans;
}
}
namespace Work{
void main(){
for(int i=1;i<=n;++i){
g[i]=BIT::query(d[i]-1);
h[i]=i-1-BIT::query(d[i]);
BIT::add(d[i],1);
sum_g[i]=sum_g[i-1]+g[i];
sum_h[i]=sum_h[i-1]+h[i];
}
block=Maxb;
Block::block=Maxb;
sort(q+1,q+1+m);
int pos_l=1,pos_r=0;
for(int i=1;i<=m;++i){
if(pos_r<q[i].r){
qu[++qu_len]=Operation(pos_l-1,pos_r+1,q[i].r,0,-q[i].id);
answer[q[i].id]+=sum_h[q[i].r]-sum_h[pos_r];
}
else if(pos_r>q[i].r){
qu[++qu_len]=Operation(pos_l-1,q[i].r+1,pos_r,0,q[i].id);
answer[q[i].id]-=sum_h[pos_r]-sum_h[q[i].r];
}
pos_r=q[i].r;
if(pos_l<q[i].l){
qu[++qu_len]=Operation(pos_r,pos_l,q[i].l-1,1,-q[i].id);
answer[q[i].id]+=sum_g[q[i].l-1]-sum_g[pos_l-1];
}
else if(pos_l>q[i].l){
qu[++qu_len]=Operation(pos_r,q[i].l,pos_l-1,1,q[i].id);
answer[q[i].id]-=sum_g[pos_l-1]-sum_g[q[i].l-1];
}
pos_l=q[i].l;
}
sort(qu+1,qu+1+qu_len);
int last=0;
Block::block=Maxb;
for(int i=1;i<=qu_len;++i){
for(int j=last+1;j<=qu[i].pos;++j){
Block::add(d[j],1);
}
last=qu[i].pos;
for(int j=qu[i].l;j<=qu[i].r;++j){
if(qu[i].id<0){
if(qu[i].op==0){
answer[-qu[i].id]-=Block::query(d[j]+1,d_len);
}
else{
answer[-qu[i].id]-=Block::query(1,d[j]-1);
}
}
else{
if(qu[i].op==0){
answer[qu[i].id]+=Block::query(d[j]+1,d_len);
}
else{
answer[qu[i].id]+=Block::query(1,d[j]-1);
}
}
}
}
for(int i=1;i<=m;++i){
answer[q[i].id]+=answer[q[i-1].id];
}
}
}
struct Segment_Node{
int lson,rson;
int sum;
}seg[Maxn*20+5];
int id_tot;
int Root[Maxn+5];
void insert(int last,int &root,int x,int a,int left=1,int right=d_len){
root=++id_tot;
seg[root]=seg[last];
seg[root].sum+=a;
if(left==right){
return;
}
int mid=(left+right)>>1;
if(x<=mid){
insert(seg[last].lson,seg[root].lson,x,a,left,mid);
}
else{
insert(seg[last].rson,seg[root].rson,x,a,mid+1,right);
}
}
int query(int root_1,int root_2,int l,int r,int left=1,int right=d_len){
if(root_2==0||l>r||l>right||r<left){
return 0;
}
if(l<=left&&r>=right){
return seg[root_2].sum-seg[root_1].sum;
}
int mid=(left+right)>>1;
return query(seg[root_1].lson,seg[root_2].lson,l,r,left,mid)+query(seg[root_1].rson,seg[root_2].rson,l,r,mid+1,right);
}
void find_ans(int l,int r,int id,int flag){
int tmp=0,now;
tmp=(s_c_1[r]-s_c_1[l-1]+Mod)%Mod;
tmp=(tmp-1ll*(s_c_0[r]-s_c_0[l-1]+Mod)*(l-1)%Mod+Mod)%Mod;
now=(s_c_2[l-1]-s_c_2[r]+Mod)%Mod;
if(l-1==0){
now=(now-1ll*s_c_0[r-1]*(n-r+1)%Mod+Mod)%Mod;
}
else{
now=(now-1ll*(s_c_0[r-1]-s_c_0[l-2]+Mod)*(n-r+1)%Mod+Mod)%Mod;
}
tmp=(tmp-now+Mod)%Mod;
q[++m].l=l;
q[m].r=r-1;
q[m].id=m;
q_id[m]=id;
q_flag[m]=flag;
tmp=(tmp-query(Root[l-1],Root[r],1,d[l-1]-1)+Mod)%Mod;
tmp=(tmp-query(Root[l-1],Root[r-1],d[r]+1,d_len)+Mod)%Mod;
/*for(int i=l;i<r;i++){
for(int j=i;j<r;j++){
tmp=(tmp+(-(d[j]<d[i])+Mod))%Mod;
}
}*/
tmp=(tmp<<1)%Mod;
now=(s_ak[r]-s_ak[l-1]+Mod)%Mod;
tmp=(tmp-now+Mod)%Mod;
tmp=1ll*tmp*flag%Mod;
ans[id]=(ans[id]+tmp)%Mod;
}
void calc(int l_1,int r_1,int l_2,int r_2,int id,int flag){
if(l_1>r_1||l_2>r_2||flag==0){
return;
}
if(l_1==l_2&&r_1==r_2){
find_ans(l_1,r_1,id,flag);
return;
}
if(l_1>l_2||(l_1==l_2&&r_1<r_2)){
swap(l_1,l_2);
swap(r_1,r_2);
}
if(r_1>=r_2){
if(r_1==r_2){
calc(l_2,r_2,l_2,r_2,id,flag);
calc(l_2,r_2,l_1,l_2-1,id,flag);
return;
}
if(l_1==l_2){
calc(l_2,r_2,l_2,r_2,id,flag);
calc(l_2,r_2,r_2+1,r_1,id,flag);
return;
}
calc(l_2,r_2,l_1,r_2,id,flag);
calc(l_2,r_2,r_2+1,r_1,id,flag);
return;
}
if(l_2>r_1){
if(l_2==r_1+1){
int now_1=flag,now_2=Mod-flag;
now_1=1ll*now_1*inv_2%Mod;
now_2=1ll*now_2*inv_2%Mod;
calc(l_1,r_2,l_1,r_2,id,now_1);
calc(l_1,r_1,l_1,r_1,id,now_2);
calc(l_2,r_2,l_2,r_2,id,now_2);
return;
}
calc(l_1,r_1,r_1+1,r_2,id,flag);
calc(l_1,r_1,r_1+1,l_2-1,id,Mod-flag);
return;
}
calc(l_1,l_2-1,l_2,r_2,id,flag);
calc(l_2,r_1,l_2,r_2,id,flag);
}
int main(){
read(n),read(Q),read(k);
for(int i=1;i<=n;i++){
read(a[i]);
sum[i]=(sum[i-1]+a[i]);
c[i]=(sum[i]/k)%Mod;
d[i]=sum[i]%k;
s_ak[i]=(s_ak[i-1]+a[i]/k)%Mod;
s_c_0[i]=(s_c_0[i-1]+c[i])%Mod;
s_c_1[i]=(s_c_1[i-1]+1ll*c[i]*i)%Mod;
_d[++d_len]=d[i];
}
sort(_d+1,_d+1+d_len);
d_len=unique(_d+1,_d+1+d_len)-_d-1;
for(int i=1;i<=n;i++){
d[i]=lower_bound(_d+1,_d+1+d_len,d[i])-_d;
insert(Root[i-1],Root[i],d[i],1);
}
for(int i=n;i>0;i--){
s_c_2[i]=(s_c_2[i+1]+1ll*(n-i+1)*c[i])%Mod;
}
s_c_2[0]=s_c_2[1];
for(int i=1;i<=Q;i++){
int x_1,y_1,x_2,y_2;
read(x_1),read(y_1),read(x_2),read(y_2);
calc(x_1,x_2,y_1,y_2,i,1);
}
Work::main();
for(int i=1;i<=m;i++){
int tmp=answer[i]%Mod;
tmp=(tmp<<1)%Mod;
tmp=1ll*tmp*q_flag[i]%Mod;
ans[q_id[i]]=(ans[q_id[i]]-tmp+Mod)%Mod;
}
for(int i=1;i<=Q;i++){
printf("%d
",ans[i]);
}
return 0;
}