题解 P3962 【[TJOI2013]数字根】
Tsuku_yomi · · 题解
蒟蒻第一次a紫题，来整篇题解，如有不足，斗胆请各位犇犇斧正
题面解析
给出一串数列，有n次询问，每次询问一个区间中所有连续子区间的和的数字根的前五大值。
解法思考
多区间询问问题很容易让我们想到使用线段树来维护区间，同时，我们根据数字根的性质很容易了解数字根的取值范0~9，所以我们对数字根状态压缩。
接下来的重点是如何储存和合并节点的问题，我们根据最大连续子区间和的线段树做法，易知：一个区间中的所有连续子区间，可以由 两个子区间的所有连续子区间 并 左子区间中以右端点作为终点的连续子区间和右子区间中以左端点作为起点的连续子区间的两两组合形成的子区间 表示。
所以如果我们可以维护一个区间中所有连续子区间all，以左端点为起点的所有连续子区间l，以右端点为终点的所有连续子区间r，那么我们就可以维护其父节点的所有连续子区间。
随后容易证得，父区间的r可以由右区间的l与整个左区间sum组合的 并 右区间的r得到，l同理，而整个父区间只需要由两个子区间就可以组合而成。
由此我们成功分解了区间节点，并解决了他们的合并问题，接下来只需要套入线段树，此题就可以迎刃而解了
以下是月读的ac代码
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstdlib>
using namespace std;
typedef long long loli;
const int MAXW=1000000;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const char test[]="test\n";
int in();
struct Node {
int l,r,lp,rp,all,sum;
Node(int _l=0,int _r=0) {
lp=_l;
rp=_r;
}
} Tr[400010];
int askroot(int i){
return 1<<((i-1)%9+1);
}
int simpleHB(int al,int ar) {
int rtn=0;
for(int i=0; i<10; ++i) {
if((al&(1<<i))) {
for(int r=0; r<10-i; ++r) {
if((ar&(1<<r)))
rtn|=(1<<(i+r));
}
for(int r=10-i; r<10; ++r) {
if((ar&(1<<r)))
rtn|=(1<<(i+r-9));
}
}
}
return rtn;
}
Node HB(Node& NL,Node& NR) {
Node rtn=Node(NL.lp,NR.rp);
rtn.all=simpleHB(NL.r,NR.l)|NL.all|NR.all;
rtn.l=NL.l|simpleHB(NL.sum,NR.l);
rtn.r=NR.r|simpleHB(NR.sum,NL.r);
rtn.sum=simpleHB(NL.sum,NR.sum);
return rtn;
}
Node BuildTr(int lp,int rp,int i){
//cout<<lp<<" "<<rp<<endl;
if(lp==rp){
Tr[i]=Node(lp,rp);
Tr[i].l=Tr[i].r=Tr[i].all=Tr[i].sum=askroot(in());
return Tr[i];
}
Node L=BuildTr(lp,(lp+rp)/2,i<<1);
Node R=BuildTr((lp+rp)/2+1,rp,(i<<1)+1);
Tr[i]=HB(L,R);
return Tr[i];
}
Node ask(int lp,int rp,int i){
if(lp<=Tr[i].lp&&rp>=Tr[i].rp){
return Tr[i];
}
if(lp<=(Tr[i].lp+Tr[i].rp)/2&&rp>(Tr[i].lp+Tr[i].rp)/2){
Node L=ask(lp,rp,i<<1);
Node R=ask(lp,rp,(i<<1)+1);
return HB(L,R);
}
if(lp<=(Tr[i].lp+Tr[i].rp)/2){
return ask(lp,rp,i<<1);
}else{
return ask(lp,rp,(i<<1)+1);
}
}
int n,q;
int askL,askR;
int main() {
n=in();
BuildTr(1,n,1);
q=in();
for(int i=0;i<q;++i){
askL=in();askR=in();
Node askend=ask(askL,askR,1);
int ptr=0,out[10];
for(int i=0;i<10;++i){
out[i]=-1;
}
for(int i=9;i>=0;--i){
if(askend.all&1<<i){
out[ptr]=i;
++ptr;
}
}
for(int i=0;i<5;++i){
printf("%d ",out[i]);
}
printf("\n");
}
return 0;
}
int in() {
int input;
scanf("%d",&input);
return input;
}