[BZOJ 1483][HNOI2009]梦幻布丁
做了很久了吧，但现在才写题解……（斜眼
首先记录一个起始的颜色段数，然后每种颜色都要用链表顺序记下该颜色有哪些点。然后合并的时候合并两个链表——最优策略显然是启发式合并。
但是，很多时候并不是把小链表的扔到大的里面的情况，而是恰好反过来的情况，如何处理？
这种时候，我们可以交换两个颜色的“真实身份”。合并的时候，把每个点当成它的“真实身份”处理即可。
[BZOJ 3252]攻略
近期心情不顺，坑了一堆没写的题解……（嗯我反演等回来再填坑吧（逃
好了还是说说这题吧，私以为鄙人的做法还是蛮妙的：
定义\(d(x)\)表示\(x\)到根上所有点的权值和，\(d_{max}(x)\)为\(x\)所在的子树中所有点的\(d(x)\)的最大值。对一个结点，他的所有儿子中\(d_{max}(x)\)最大的称为重儿子，其他作为轻儿子，然后做一遍树剖。然后将所有重链的权值和扔到一个数组里，降序排序，选前\(k\)大求和即可（不够的话全选）。
为什么？
显然，尽可能选叶子是划算的。然后，任意一条重链链顶的父亲所在的重链的权值和必定大于该重链，所以说不必担心某个重链选了而他的祖先却没有被记到答案里的情况。而若干这种重链的并，恰好对应了若干条到叶子路径的并。由于我们还是从大到小选的，所以答案是最优的。
[BZOJ 2599][IOI2011]Race
由于一些琐事，很长时间没有更新博客了……尽管做了不少题，但还是给我些时间整理思绪吧……
大方向肯定是点分治没错啦……
点分治的题处理经过根的路径通常有两种套路……一种是类似BZOJ 1468那样，收集所有儿子的信息，然后一次性合并，并排除不合法的情况。另一种类似于这道题，顺次处理儿子的信息，处理一个合并一个。
具体的思路是，用[tex]p[x][/tex]表示目前已知的所有从根开始长度为[tex]x[/tex]的路径（当然根本身也算上啦，所以说一开始就把[tex]p[root][/tex]设为0），然后根搜集信息时每次对一个儿子进行DFS，假设某结点[tex]x[/tex]到根的距离为[tex]d[x][/tex]，那么显然[tex]x[/tex]对答案的贡献为[tex]p[k-d[x]][/tex]，之后把这个子树合并到[tex]p[/tex]中。
注意清理[tex]p[/tex]的时候不能直接暴力memset……这样会被卡常致死。更好的方法是对于每次把子树合并到[tex]p[/tex]中时，把[tex]x[/tex]记录下来，然后清理[tex]p[/tex]时常数就小很多了。
代码：
/**************************************************************
Problem: 2599
User: danihao123
Language: C++
Result: Accepted
Time:14640 ms
Memory:23532 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 200005;
const int maxm = maxn * 2;
const int maxk = 1000005;
struct Edge {
Edge *next;
int to, dist;
};
Edge pool[maxm];
int graph_cnt;
Edge *first[maxn];
inline void clear_graph() {
graph_cnt = 0;
memset(first, 0, sizeof first);
}
inline void add_edge(int u, int v, int d) {
Edge *e = &pool[graph_cnt++];
e->next = first[u];
first[u] = e;
e->to = v;
e->dist = d;
}
int k;
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa) {
siz[x] = 1;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
gen_siz(v, x);
siz[x] += siz[v];
}
}
}
int now_root, best_root;
void gen_best_root(int x, int fa) {
bool OK = siz[x]*2 >= siz[now_root];
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
gen_best_root(v, x);
OK = OK && (siz[v]*2 <= siz[now_root]);
}
}
if(OK) {
best_root = x;
}
}
int buf[maxk];
int ans;
void deal_ans(int x, int fa, int dep, int d) {
if(d > k) {
return;
}
ans = min(ans, dep + buf[k-d]);
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
deal_ans(v, x, dep + 1, d + e->dist);
}
}
}
void add_to_buf(int x, int fa, int dep, int d) {
if(d > k) {
return;
}
buf[d] = min(buf[d], dep);
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
add_to_buf(v, x, dep + 1, d + e->dist);
}
}
}
void clear_buf(int x, int fa, int dep, int d) {
if(d > k) {
return;
}
buf[d] = 0x3f3f3f3f;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
clear_buf(v, x, dep + 1, d + e->dist);
}
}
}
void divide(int x) {
gen_siz(x, 0);
now_root = best_root = x; gen_best_root(x, 0);
x = best_root;
vis[x] = true;
buf[0] = 0;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v]) {
deal_ans(v, x, 1, e->dist);
add_to_buf(v, x, 1, e->dist);
}
}
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v]) {
clear_buf(v, x, 1, e->dist);
}
}
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v]) {
divide(v);
}
}
}
inline int readint() {
int x = 0;
char c = getchar();
while(!isdigit(c)) {
c = getchar();
}
while(isdigit(c)) {
x = x * 10 + (c - '0');
c = getchar();
}
return x;
}
int main() {
int n;
n = readint();
k = readint();
clear_graph();
for(int i = 1; i <= (n-1); i++) {
int u, v, d;
u = readint();
v = readint();
d = readint();
u++; v++;
add_edge(u, v, d);
add_edge(v, u, d);
}
ans = 0x3f3f3f3f;
memset(buf, 0x3f, sizeof buf);
divide(1);
if(ans == 0x3f3f3f3f) {
ans = -1;
}
printf("%d\n", ans);
return 0;
}
[POJ 1149]PIGS
这个题是经典的网络流题目。在经过一次次的思想过滤后你会发现，这个问题的瓶颈（换猪）大可以理解为前面的顾客给后面的留一些不是？这样问题就简单多了。
按顺序整理出到访每个猪圈的顾客，对于到访每个猪圈的第一个顾客，从[tex]S[/tex]向其连一条容量为此猪圈中猪的数量的边。然后每个猪圈前面一个顾客要个给后面的留一些猪，这个可以直接连一条容量为无限大的边来表示。
最后每个顾客向[tex]T[/tex]连一条容量为其买猪数量上限的边，然后求一遍[tex]S[/tex]到[tex]T[/tex]的最大流，问题得解。
这个题还有一个优化就是，有一些边是可以合并的（比如说从[tex]S[/tex]流出的一些边是可能指向同一顾客的，同一对顾客之间的连边数可能不止1条），但是我没有做这个优化，照样A了……
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using std::vector;
using std::queue;
using std::min;
const int maxn=105,maxm=1005;
namespace Dinic{
struct Edge{
int u,v,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int s,t;
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn];
inline bool bfs(){
register int i,u,siz;
queue<int> Q;
memset(vis,0,sizeof(vis));
d[s]=0;
Q.push(s);
vis[s]=true;
while(!Q.empty()){
u=Q.front();Q.pop();
siz=G[u].size();
for(i=0;i<siz;i++){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
d[e.v]=d[u]+1;
Q.push(e.v);
vis[e.v]=true;
}
}
}
return vis[t];
}
int cur[maxn];
int dfs(int x,int a){
if(x==t || a==0){
return a;
}
int f,flow=0,siz=G[x].size();
for(int& i=cur[x];i<siz;i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
f=dfs(e.v,min(a,e.cap-e.flow));
if(f>0){
flow+=f;
e.flow+=f;
edges[G[x][i]^1].flow-=f;
a-=f;
if(a==0){
break;
}
}
}
}
if(a>0){
d[x]=-1;
}
return flow;
}
inline int solve(int S,int T){
register int ans=0;
s=S;t=T;
while(bfs()){
memset(cur,0,sizeof(cur));
ans+=dfs(s,0x7fffffff);
}
return ans;
}
};
using Dinic::AddEdge;
using Dinic::solve;
int pigs[maxm];
vector<int> Use[maxm];
int main(){
register int i,j;
int m,n;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++){
scanf("%d",&pigs[i]);
}
for(i=1;i<=n;i++){
int a,b,temp;
scanf("%d",&a);
for(j=1;j<=a;j++){
scanf("%d",&temp);
Use[temp].push_back(i);
}
scanf("%d",&b);
AddEdge(i,n+1,b);
}
for(i=1;i<=m;i++){
AddEdge(0,Use[i][0],pigs[i]);
int siz=Use[i].size();
for(j=1;j<siz;j++){
AddEdge(Use[i][j-1],Use[i][j],0x7f7f7f7f);
}
}
printf("%d\n",solve(0,n+1));
return 0;
}
[BZOJ 1086][SCOI2005]王室联邦
最近想捉一下树分块，这道题肯定是要做的啦~
这个题的方法就是蜜汁贪心，在其他树分块的题目中也有应用。
代码：
/**************************************************************
Problem: 1086
User: danihao123
Language: C++
Result: Accepted
Time:16 ms
Memory:880 kb
****************************************************************/
#include <cstdio>
#include <stack>
using std::stack;
const int maxn=1005;
const int maxm=maxn*2;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int belong[maxn],cap[maxn];
int block_cnt=0;
stack<int> S;
int B;
void DFS(int u,int fa){
int siz=S.size();
for(int i=first[u];i;i=next[i]){
int v=to[i];
if(v==fa){
continue;
}
DFS(v,u);
if((S.size()-siz)>=B){
block_cnt++;
cap[block_cnt]=u;
while(S.size()>siz){
int x=S.top();S.pop();
belong[x]=block_cnt;
}
}
}
S.push(u);
}
int main(){
register int i;
bool OK;
int n,u,v;
scanf("%d%d",&n,&B);
for(i=1;i<=(n-1);i++){
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
if(n<B){
puts("0");
return 0;
}
DFS(1,0);
while(!S.empty()){
int x=S.top();S.pop();
belong[x]=block_cnt;
}
printf("%d\n",block_cnt);
OK=false;
for(i=1;i<=n;i++){
if(OK){
putchar(' ');
}
OK=true;
printf("%d",belong[i]);
}
putchar('\n');
OK=false;
for(i=1;i<=block_cnt;i++){
if(OK){
putchar(' ');
}
OK=true;
printf("%d",cap[i]);
}
putchar('\n');
return 0;
}
[BZOJ 1009][HNOI2008]GT考试
好劲啊这题……
首先先想DP的做法，我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex]，有多少种方案使得追加上一个数后匹配[tex][1,j][/tex]，这个用KMP可以很方便的求出（事实上暴力也可以）。
然后再来看DP的做法，转移方程大致是这样的：
[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]
但是n非常大，这么做注定要TLE。
不过看这个转移方程，是不是和矩阵乘法的定义很像？是的。
我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值，我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现：
[tex]D_i\times P=D_{i+1}[/tex]
由于矩阵乘法满足结合律，所以：
[tex]D_n=D_0\times P^n[/tex]
很明显可以快速幂搞出来。
代码：
/**************************************************************
Problem: 1009
User: danihao123
Language: C++
Result: Accepted
Time:80 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
register int i,j,k;
Matrix C;
CL_ARR(C,0);
REP(i,m){
REP(j,p){
REP(k,n){
C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
}
}
}
CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
Matrix a,temp;
register int i;
CL_ARR(a,0);
memcpy(a,A,sizeof(a));
CL_ARR(temp,0);
REP(i,m){
temp[i][i]=1;
}
while(p){
if(1&p){
MatrixMul(temp,a,m,m,m,temp);
}
p>>=1;
MatrixMul(a,a,m,m,m,a);
}
CP_ARR(temp,res);
}
char buf[25];
int f[25];
int main(){
register int i,u,j;
register ull ret=0;
ull n;
int m;
Matrix ans,P;
scanf("%llu%d%llu",&n,&m,&MOD);
scanf("%s",buf+1);
CL_ARR(ans,0);
ans[0][0]=1;
CL_ARR(P,0);
P[0][0]=9;P[0][1]=1;
// f[0]=f[1]=0;
for(i=1;i<m;i++){
u=f[i];
while(u && buf[u+1]!=buf[i+1]){
u=f[u];
}
if(buf[u+1]==buf[i+1]){
f[i+1]=u+1;
}else{
f[i+1]=0;
}
for(j=0;j<10;j++){
u=i;
while(u && buf[u+1]!=j+'0'){
u=f[u];
}
if(buf[u+1]==j+'0'){
P[i][u+1]=(P[i][u+1]+1)%MOD;
}else{
P[i][0]=(P[i][0]+1)%MOD;
}
}
}
MatrixPow(P,m,n,P);
MatrixMul(ans,P,1,m,m,ans);
for(i=0;i<m;i++){
ret=(ret+ans[0][i])%MOD;
}
printf("%llu\n",ret);
return 0;
}
[BZOJ 1176][Balkan2007]Mokia
CDQ分治第一题……同时也是CDQ分治模板提。
感觉CDQ分治思路好秒啊……似乎在分治过程中做了个归并排序……
代码：
/**************************************************************
Problem: 1176
User: danihao123
Language: C++
Result: Accepted
Time:4364 ms
Memory:17228 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxw=2000005;
const int maxq=10005;
const int maxn=160001+4*maxq;
int cnt=0;
struct Query{
int ans_id;
int x,y,d,v;
Query(){}
Query(int a,int b,int di,int ap){
x=a;y=b;
d=di;
ans_id=ap;
}
Query(int a,int b,int value){
x=a;y=b;
v=value;
d=0;
}
inline bool isQuery(){
return d!=0;
}
};
int w;
int T[maxw];
inline int lowbit(int x){
return x&(-x);
}
inline void add(int p,int v){
while(p<=w){
T[p]+=v;
p+=lowbit(p);
}
}
inline int sum(int p){
register int x=0;
while(p>0){
x+=T[p];
p-=lowbit(p);
}
return x;
}
inline void clear(int p){
while(p<=w && T[p]!=0){
T[p]=0;
p+=lowbit(p);
}
}
Query Q[maxn],tmp[maxn];
int ans[maxn];
void CDQ(int L,int R){
if(L==R){
return;
}
int M=L+(R-L)/2;
CDQ(L,M);
CDQ(M+1,R);
int p,p1,p2;
for(p=1,p1=L,p2=M+1;p<=(R-L+1);p++){
if((Q[p1].x<=Q[p2].x && p1<=M) || p2>R){
tmp[p]=Q[p1];
if(!Q[p1].isQuery()){
add(Q[p1].y,Q[p1].v);
}
p1++;
}else{
tmp[p]=Q[p2];
if(Q[p2].isQuery()){
ans[Q[p2].ans_id]+=sum(Q[p2].y)*Q[p2].d;
}
p2++;
}
}
for(p=1,p1=L;p<=(R-L+1);p++,p1++){
if(!Q[p1].isQuery()){
clear(Q[p1].y);
}
Q[p1]=tmp[p];
}
}
int main(){
int S,t,x,y,a,b;
register int ans_cnt=0;
scanf("%d%d",&S,&w);
while(true){
scanf("%d",&t);
if(t==3){
break;
}
scanf("%d%d%d",&x,&y,&a);
// x++;y++;
if(t==1){
Q[++cnt]=Query(x,y,a);
}else{
scanf("%d",&b);
// a++;b++;
ans_cnt++;
ans[ans_cnt]=(a-x+1)*(b-y+1)*S;
Q[++cnt]=Query(a,b,1,ans_cnt);
Q[++cnt]=Query(x-1,b,-1,ans_cnt);
Q[++cnt]=Query(a,y-1,-1,ans_cnt);
Q[++cnt]=Query(x-1,y-1,1,ans_cnt);
}
}
CDQ(1,cnt);
for(register int i=1;i<=ans_cnt;i++){
printf("%d\n",ans[i]);
}
return 0;
}
[BZOJ 2653]middle
前几天想用Github+org-mode替代这个博客，后来想了想，还是算了吧。毕竟博客对大家更方便。
这个题真不愧是陈老师的题啊……exciting！
首先我们看到左端点在[tex][a,b][/tex]，右端点在[tex][c,d][/tex]，一股GSS5的气味扑来？
为了方便，我们先将序列离散化。然后我们将序列中大于等于x的值变为1，小于x的值变为-1，则某段区间的区间和若大于等于0，则该区间的中位数大于等于x，反之则其中位数小于x（注意，此题的中位数定义比较奇怪）。
然后我们可以对每个x建一棵树，然后二分答案，对于每个答案在对应的树上跑一遍GSS5即可（不过这题[tex]a<b<c<d[/tex]，所以不需要复杂的分类讨论）。
但是如果每个x都建一棵树，肯定会MLE吧？这个时候就要用主席树了= =
代码：
/**************************************************************
Problem: 2653
User: danihao123
Language: C++
Result: Accepted
Time:2220 ms
Memory:1956 kb
****************************************************************/
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=20005;
struct Node{
Node *lc,*rc;
int maxPSum,maxSSum,sum;
Node(int x){
lc=rc=NULL;
maxPSum=maxSSum=sum=x;
}
Node(Node *l,Node *r){
lc=l;rc=r;
}
void maintain(){
maxPSum=max(lc->maxPSum,lc->sum+rc->maxPSum);
maxSSum=max(rc->maxSSum,rc->sum+lc->maxSSum);
sum=lc->sum+rc->sum;
}
};
Node* build_tree(int L,int R){
if(L==R){
return new Node(1);
}
int M=L+(R-L)/2;
Node *ans=new Node(build_tree(L,M),build_tree(M+1,R));
ans->maintain();
return ans;
}
int p,v;
Node* insert(Node *o,int L,int R){
if(L==R){
return new Node(v);
}else{
Node *ans=new Node(o->lc,o->rc);
int M=L+(R-L)/2;
if(p<=M){
ans->lc=insert(ans->lc,L,M);
}else{
ans->rc=insert(ans->rc,M+1,R);
}
ans->maintain();
return ans;
}
}
int ql,qr;
Node queryPSum(Node *o,int L,int R){
if(ql<=L && R<=qr){
return *o;
}else{
int M=L+(R-L)/2;
if(qr<=M){
return queryPSum(o->lc,L,M);
}else{
if(ql<=M){
Node l=queryPSum(o->lc,L,M);
Node r=queryPSum(o->rc,M+1,R);
Node ans(l.sum+r.sum);
ans.maxPSum=max(l.maxPSum,l.sum+r.maxPSum);
return ans;
}else{
return queryPSum(o->rc,M+1,R);
}
}
}
}
Node querySSum(Node *o,int L,int R){
if(ql<=L && R<=qr){
return *o;
}else{
int M=L+(R-L)/2;
if(qr<=M){
return querySSum(o->lc,L,M);
}else{
if(ql<=M){
Node l=querySSum(o->lc,L,M);
Node r=querySSum(o->rc,M+1,R);
Node ans(l.sum+r.sum);
ans.maxSSum=max(r.maxSSum,r.sum+l.maxSSum);
return ans;
}else{
return querySSum(o->rc,M+1,R);
}
}
}
}
int querySum(Node *o,int L,int R){
if(ql<=L && R<=qr){
return o->sum;
}else{
int M=L+(R-L)/2;
int ans=0;
if(ql<=M){
ans+=querySum(o->lc,L,M);
}
if(qr>M){
ans+=querySum(o->rc,M+1,R);
}
return ans;
}
}
Node *root[maxn];
int n;
int A[maxn],A2[maxn];
vector<int> V[maxn];
int lsh_siz;
inline void lsh(){
sort(A2+1,A2+1+n);
lsh_siz=unique(A2+1,A2+1+n)-A2-1;
for(register int i=1;i<=n;i++){
A[i]=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
V[A[i]].push_back(i);
}
}
int q[4];
inline bool Check(int M){
register int l,m,r;
if(q[1]+1<=q[2]-1){
ql=q[1]+1;
qr=q[2]-1;
m=querySum(root[M],1,lsh_siz);
}else{
m=0;
}
ql=q[0];qr=q[1];
l=querySSum(root[M],1,lsh_siz).maxSSum;
ql=q[2];qr=q[3];
r=queryPSum(root[M],1,lsh_siz).maxPSum;
#ifdef DEBUG
printf("Case %d: %d %d %d\n",M,l,m,r);
#endif
return l+m+r>=0;
}
int main(){
register int i,j,L,M,R,ans=0;
int t;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
A2[i]=A[i];
}
lsh();
root[1]=build_tree(1,n);
for(i=2;i<=lsh_siz;i++){
root[i]=root[i-1];
for(j=0;j<V[i-1].size();j++){
p=V[i-1][j];
v=-1;
root[i]=insert(root[i],1,lsh_siz);
}
}
scanf("%d",&t);
while(t--){
for(i=0;i<4;i++){
scanf("%d",&q[i]);
q[i]=(q[i]+ans)%n;
}
sort(q,q+4);
for(i=0;i<4;i++){
q[i]++;
#ifdef DEBUG
printf("%d ",q[i]);
if(i==3){
puts("");
}
#endif
}
L=1;R=lsh_siz;
while(true){
if(R-L<=3){
for(i=R;i>=L;i--){
if(Check(i)){
ans=A2[i];
break;
}
}
break;
}
M=L+(R-L)/2;
if(Check(M)){
L=M;
}else{
R=M;
}
}
printf("%d\n",ans);
}
return 0;
}
[BZOJ 2038]小Z的袜子
今年第一更……噫
终于学会莫队了，不过目前只能做这样的模板题……
代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
using namespace std;
const int maxn=50005;
typedef long long ll;
ll gcd(ll a,ll b){
if(!b){
return a;
}else{
return gcd(b,a%b);
}
}
ll C2(ll n){
register ll temp,ns1=n-1;
if(n&1){
temp=ns1>>1;
return temp*n;
}else{
temp=n>>1;
return temp*ns1;
}
}
struct Node{
int L_s;
int L,R;
int id;
ll ans1,ans2;
};
bool cmp1(const Node& a,const Node& b){
if(a.L_s==b.L_s){
return a.R<b.R;
}else{
return a.L_s<b.L_s;
}
}
bool cmp2(const Node& a,const Node& b){
return a.id<b.id;
}
Node Q[maxn];
int C[maxn],d[maxn];
int n,m;
inline void add_p(int x,ll &ans){
d[x]++;
ans+=d[x]-1;
}
inline void sub_p(int x,ll &ans){
d[x]--;
ans-=d[x];
}
inline void Mo(){
register int i,j,L_p,R_p,sqrt_n=sqrt(n+0.5);
register ll ans,t_gcd,t2;
for(i=1;i<=m;i++){
Q[i].L_s=Q[i].L/sqrt_n;
}
sort(Q+1,Q+1+m,cmp1);
L_p=R_p=Q[1].L;
ans=0;
d[C[L_p]]++;
for(i=1;i<=m;i++){
while(L_p<Q[i].L){
sub_p(C[L_p],ans);
L_p++;
}
while(L_p>Q[i].L){
L_p--;
add_p(C[L_p],ans);
}
while(R_p<Q[i].R){
R_p++;
add_p(C[R_p],ans);
}
while(R_p>Q[i].R){
sub_p(C[R_p],ans);
R_p--;
}
t2=C2(R_p-L_p+1);
t_gcd=gcd(ans,t2);
Q[i].ans1=ans/t_gcd;
Q[i].ans2=t2/t_gcd;
}
sort(Q+1,Q+1+m,cmp2);
}
int main(){
register int i;
int a,b;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&C[i]);
}
for(i=1;i<=m;i++){
Q[i].id=i;
scanf("%d%d",&a,&b);
Q[i].L=a;
Q[i].R=b;
}
Mo();
for(i=1;i<=m;i++){
printf("%lld/%lld\n",Q[i].ans1,Q[i].ans2);
}
return 0;
}
[BZOJ 1798]维护序列
万年不更的zzs出现了……
这个题以前竟然没做……近几天做了一下，首交竟然unAC……看样子是我真不会线段树了。
这题不难，唯一需要注意的是乘法标记对加法标记也有影响，而且下传要乘法优先。
代码（警告：此代码exciting）：
/**************************************************************
Problem: 1798
User: danihao123
Language: C++
Result: Accepted
Time:7696 ms
Memory:10980 kb
****************************************************************/
#include <cstdio>
typedef long long ll;
const int maxn=100005;
ll ha;
struct Node{
ll sumv;
int L,R;
ll addv,mulv;
Node *lc,*rc;
Node(ll v,int pos){
sumv=v%ha;
addv=0;
mulv=1;
L=R=pos;
lc=rc=NULL;
}
Node(Node *l,Node *r,int Le,int Ri){
sumv=0;
addv=0;
mulv=1;
L=Le;
R=Ri;
lc=l;
rc=r;
}
void paint_add(ll v){
v=v%ha;
addv=(addv+v)%ha;
ll add_v=(v*((R-L+1)%ha))%ha;
sumv=(sumv+add_v)%ha;
}
void paint_mul(ll v){
v=v%ha;
addv=(addv*v)%ha;
mulv=(mulv*v)%ha;
sumv=(sumv*v)%ha;
}
void maintain(){
if(lc!=NULL && rc!=NULL){
sumv=(lc->sumv+rc->sumv)%ha;
}
}
void pushdown(){
if(mulv!=1){
if(lc!=NULL){
lc->paint_mul(mulv);
}
if(rc!=NULL){
rc->paint_mul(mulv);
}
mulv=1;
}
if(addv!=0){
if(lc!=NULL){
lc->paint_add(addv);
}
if(rc!=NULL){
rc->paint_add(addv);
}
addv=0;
}
}
};
ll A[maxn];
void build_tree(Node* &o,int L,int R){
if(L==R){
o=new Node(A[L],L);
}else{
int M=L+(R-L)/2;
Node *lc,*rc;
build_tree(lc,L,M);
build_tree(rc,M+1,R);
o=new Node(lc,rc,L,R);
o->maintain();
}
}
Node *root;
int ql,qr;
ll v;
ll query_sum(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
return o->sumv;
}else{
int M=L+(R-L)/2;
ll ans=0;
if(ql<=M){
ans=(ans+query_sum(o->lc))%ha;
}
if(qr>M){
ans=(ans+query_sum(o->rc))%ha;
}
return ans;
}
}
void update_add(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
o->paint_add(v);
}else{
int M=L+(R-L)/2;
if(ql<=M){
update_add(o->lc);
}
if(qr>M){
update_add(o->rc);
}
o->maintain();
}
}
void update_mul(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
o->paint_mul(v);
}else{
int M=L+(R-L)/2;
if(ql<=M){
update_mul(o->lc);
}
if(qr>M){
update_mul(o->rc);
}
o->maintain();
}
}
int main(){
register int i;
int n,m,op;
scanf("%d%lld",&n,&ha);
// ha=0x7fffffff;
for(i=1;i<=n;i++){
scanf("%lld",&A[i]);
}
build_tree(root,1,n);
scanf("%d",&m);
while(m--){
scanf("%d%d%d",&op,&ql,&qr);
if(ha==1){
if(op==3){
puts("0");
}else{
scanf("%lld",&v);
}
continue;
}
if(op==1){
scanf("%lld",&v);
update_mul(root);
}else{
if(op==2){
scanf("%lld",&v);
update_add(root);
}else{
printf("%lld\n",query_sum(root));
}
}
}
return 0;
}
