手机网站建设套餐内容,网页是怎么做的,大兴网站开发网站建设咨询,做招聘网站赚钱吗【BZOJ4262】Sum Description Input 第一行一个数 t#xff0c;表示询问组数。第一行一个数 t#xff0c;表示询问组数。接下来 t 行#xff0c;每行四个数 l_1, r_1, l_2, r_2。Output 一共 t 行#xff0c;每行一个数 Sum。Sample Input 4 1 3 5 7 2 4 6 8 1 1 9 9 9 9 1…【BZOJ4262】Sum Description Input 第一行一个数 t表示询问组数。 第一行一个数 t表示询问组数。 接下来 t 行每行四个数 l_1, r_1, l_2, r_2。 Output 一共 t 行每行一个数 Sum。 Sample Input 4 1 3 5 7 2 4 6 8 1 1 9 9 9 9 1 1 Sample Output 9322587654 9025304064 1065645568 0 HINT 1t40000,1L1R110^5,1L2R210^5 题解我们分开考虑max和pre的情况。我们将max(i...j)视为二维平面上点(i,j)的权值处理出每个数左边第一个比它大的数然后这个数的贡献区间可以就看成一个矩形或三角形而询问就变成了求平面上一个矩形区域的权值和。可以用线段树来搞。 不过线段树维护历史总和还真是不容易打标记的部分还是好好说说吧。 维护三个值v代表当前的区间和s代表历史的v之和l代表区间长度。维护四个标记a,b,c,d代表标记生效后va*vb*lssc*vd*l。 关键在于标记如何合并。假如我们要将x和y的标记合并成z。 a显然z.ax.a*y.a即可。b先要*y.a还要y.b。cx.a*y.c。d先要y.d还要x.b*y.c。 #include cstdio
#include cstring
#include iostream
#include algorithm
#define lson x1
#define rson x1|1
using namespace std;
const int maxn100010;
typedef long long ll;
struct Tag
{ll a,b,c,d;Tag () {a1,bcd0;}Tag (ll A,ll B,ll C,ll D) {aA,bB,cC,dD;}Tag operator (const Tag x) const {return Tag(a*x.a,b*x.ax.b,a*x.cc,db*x.cx.d);}
};
struct node
{ll v,s,l;Tag t;node () {vsl0,tTag();}node (ll a,ll b,ll c,Tag d) {va,sb,lc,td;}inline void add(Tag x){ssv*x.cl*x.d,vv*x.al*x.b,ttx;}node operator (const node a) const{return node(va.v,sa.s,la.l,Tag());}
}s[maxn2];
int m,n,top;
ll ans[maxn],v[maxn];
int st[maxn],pre[maxn];
struct QUERY
{int x,l,r,org,k;
}q[maxn];
bool cmp(const QUERY a,const QUERY b)
{return a.xb.x;
}
inline void pushdown(int x)
{if(s[x].t.a!1||s[x].t.b||s[x].t.c||s[x].t.d) s[lson].add(s[x].t),s[rson].add(s[x].t),s[x].tTag();
}
void build(int l,int r,int x)
{if(lr){s[x]node(),s[x].l1;return ;}int mid(lr)1;build(l,mid,lson),build(mid1,r,rson);s[x]s[lson]s[rson];
}
void updata(int l,int r,int x,int a,int b,Tag t)
{if(ab) return ;if(alrb){s[x].add(t);return ;}pushdown(x);int mid(lr)1;if(amid) updata(l,mid,lson,a,b,t);if(bmid) updata(mid1,r,rson,a,b,t);s[x]s[lson]s[rson];
}
node query(int l,int r,int x,int a,int b)
{if(alrb) return s[x];pushdown(x);int mid(lr)1;if(bmid) return query(l,mid,lson,a,b);if(amid) return query(mid1,r,rson,a,b);return query(l,mid,lson,a,b)query(mid1,r,rson,a,b);
}
void work(ll flag)
{int i,j;build(1,n,1);for(j1;j2*m!q[j].x;j);for(i1;in;i){updata(1,n,1,pre[i],i,Tag(0,v[i],0,0)),s[1].add(Tag(1,0,1,0));for(;j2*mq[j].xi;j) ans[q[j].org]flag*q[j].k*query(1,n,1,q[j].l,q[j].r).s;}
}
inline int rd()
{int ret0,f1; char gcgetchar();while(gc0||gc9) {if(gc-) f-f; gcgetchar();}while(gc0gc9) retret*10gc-0,gcgetchar();return ret*f;
}
int main()
{mrd();int i;ll t11,t21;for(i1;im;i) q[i].lq[im].lrd(),q[i].rq[im].rrd(),q[i].xrd()-1,q[im].xrd(),nmax(n,q[im].x),q[i].k-1,q[im].k1,q[i].orgq[im].orgi;for(i1;in;i) t1t1*1023%1000000000,t2t2*1025%1000000000,v[i]t1^t2;sort(q1,q2*m1,cmp);for(i1;in;i){while(topv[st[top]]v[i]) top--;pre[i]st[top]1,st[top]i;}work(-1);for(top0,i1;in;i){while(topv[st[top]]v[i]) top--;pre[i]st[top]1,st[top]i;}work(1);for(i1;im;i) printf(%lld\n,ans[i]);return 0;
} 转载于:https://www.cnblogs.com/CQzhangyu/p/7749437.html
