# Data Structure Topics - Tree Arrays, Line Segment Tree Exercises

Niu Ke Contest_ACM/NOI/CSP/CCPC/ICPC Algorithm Programming High Difficulty Practice Game_ Niu Ke Contest OJ (nowcoder.com)

### A.[NOIP2012] Borrowing classrooms

#### Topic meaning:

There are a total of n days. Every day, the school has ri classrooms available for rent. It gives you a series of rental orders, and asks you whether all the orders can be satisfied. If not, find out which plan is not satisfied.

The format of each plan is: from day L to day R, rent x rooms

Binary + tree array

The tree-like array is used to maintain the number of spare classrooms for each day, that is, differential usage

Divide a plan number mid each time, maintain all orders before mid into a tree-like array, and then check whether the number of spare classrooms obtained every day is less than 0. If there is, it means that this order can no longer be satisfied. Divide forward , otherwise bisect backwards.

If there is no illegal situation, it means that all orders can be satisfied, otherwise the divided ans is the first unsatisfied order

#### Code:

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int R(){int a=0,b=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')b=-1;c=getchar();}while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}return a*b;}
int n,m;
int a[1000010],c[1000010];
struct query{
int d,l,r;
}q[1000010];
int lb(int x){
return x&(-x);
}
for(int i=x;i<=n;i+=lb(i)){
c[i]+=d;
}
}
int Sum(int x){
int ans=0;
for(int i=x;i>0;i-=lb(i)){
ans+=c[i];
}
return ans;
}
void init(){
for(int i=1;i<=n;++i){
Add(i,a[i]); // Initialize, transfer a[i] to tree array c[i]
}
}
int last;
bool check(int now){
if(now>last){
for(int i=last+1;i<=now;++i){
}
}else if(last>now){
for(int i=last;i>=now+1;--i){
}
}
last=now;
for(int i=1;i<=n;++i){
if(Sum(i)<0)return false;
}
return true;
}
int main(){
n=R();m=R();
for(int i=1;i<=n;++i){
a[i]=R();
}
init();
for(int i=1;i<=m;++i){
q[i].d=R();q[i].l=R();q[i].r=R();
}
int L=0,R=m,mid,ans=-1;
while(L<=R){
mid=L+R>>1;
if(check(mid)){
L=mid+1;
}else{ // illegal
R=mid-1;
ans=mid;
}
}
if(ans==-1)printf("0");
else printf("%d\n%d",-1,ans);
return 0;
}
```

### B.[SDOI2009]HH's necklace

#### Topic meaning:

Give a sequence, ask m times, each time ask the number of different numbers in an interval

Offline + Tree Array

Save the query and sort it according to the right endpoint from small to large

Maintain a tree-like array:

The first time you encounter a number, add 1 directly to this position

If it is not the first time, subtract 1 from the last occurrence of this number, and add 1 to the current position,

Thus, for query [L,R], ans=sum®-sum(L-1)

#### Code:

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int R(){int a=0,b=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')b=-1;c=getchar();}while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}return a*b;}
int n,m,a[50010],la[1000010],ans[200010];
struct query{
int l,r,id;
}q[200010];
int c[50010];
int lb(int x){
return x&(-x);
}
for(int i=x;i<=n;i+=lb(i)){
c[i]+=d;
}
}
int Sum(int x){
int ans=0;
for(int i=x;i>0;i-=lb(i)){
ans+=c[i];
}
return ans;
}
void init(){
for(int i=1;i<=n;++i){
Add(i,a[i]); // Initialize, transfer a[i] to tree array c[i]
}
}
bool cmp(query a,query b){
return a.r<b.r;
}
int main(){
n=R();
for(int i=1;i<=n;++i){
a[i]=R();
}
m=R();
for(int i=1;i<=m;++i){
q[i].l=R();q[i].r=R();
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int j=1;
for(int i=1;i<=n;++i){
la[a[i]]=i;
while(i==q[j].r){
ans[q[j].id]=Sum(i)-Sum(q[j].l-1);
++j;
}
}
for(int i=1;i<=m;++i){
printf("%d\n",ans[i]);
}
return 0;
}
```

### C.[HEOI2012] Picking flowers

#### Topic meaning:

Similar to the previous question, given an array, ask m times, each time the number of [numbers] in the interval is greater than 1 [number]

Offline + Tree Array

Sort queries by left endpoint from smallest to largest

Initialize a linked list at the beginning, the next of each position points to the next position with the same number as the current position

Then add 1 to the tree array where the second occurrence of each type of number occurs

To process the query of [L,R], process all the numbers before L:

Traversing from front to back, without encountering a number, if this number appears later, then next must point to it, and after removing the current number, the number pointed to by next will become the first occurrence, not the second, so The position pointed to by next is decremented by 1 (decrement by 1 in the tree array)

If next still exists, add 1 to its position, because it becomes the new second occurrence

#### Code:

```#include <bits/stdc++.h>
using namespace std;
inline int R(){int a=0,b=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')b=-1;c=getchar();}while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}return a*b;}
const int MAXN=2000010;
int N,C,M;
int c[MAXN];
struct node{
int l,r,id;
}q[MAXN];
bool cmp(node a,node b){
return a.l<b.l;
}
for(int i=x;i<=N;i+=i&(-i)){
c[i]+=d;
}
}
int sum(int x){
int ans=0;
for(int i=x;i>=1;i-=i&(-i)){
ans+=c[i];
}
return ans;
}
int main(){
N=R();C=R();M=R();
for(int i=1;i<=N;++i){
a[i]=R();
}
for(int i=N;i>=1;--i){
}
for(int i=1;i<=M;++i){
q[i].l=R();q[i].r=R();
q[i].id=i;
}
for(int i=1;i<=C;++i){
if(t){
}
}
sort(q+1,q+1+M,cmp);
int now=1;
for(int i=1;i<=M;++i){
int l=q[i].l;
while(now<l){
int t=Next[now];
if(t){
if(Next[t]){
}
}
now++;
}
ans[q[i].id]=sum(q[i].r);
}
for(int i=1;i<=M;++i){
printf("%d\n",ans[i]);
}
return 0;
}
```

### D. Data structure

#### Topic meaning:

Line segment tree board sub-topic

​ 1 l r Query the sum of elements in the interval [l,r]

​ 2 l r Query the sum of squares of elements in the interval [l,r]

​ 3 l r x Multiply each element in the interval [l,r] by x

​ 4 l r x Add x to every element in the interval [l,r]

Familiarize yourself with the structure of the line segment tree, modular implementation, careful

#### Code:

```#include <bits/stdc++.h>
using namespace std;
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
inline ll R(){ll a=0,b=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')b=-1;c=getchar();}while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}return a*b;}
ll n,m,a[10010];
struct Tree{
ll l,r,s1,s2;
ll sum,mul;
}o[10010*4];
ll ans;
void pushup(ll i){
o[i].s1=o[ls].s1+o[rs].s1;
o[i].s2=o[ls].s2+o[rs].s2;
}
void pushdown(ll i){
ll m=o[i].mul,s=o[i].sum;
if(m!=1){
o[ls].mul*=m;
o[rs].mul*=m;
o[ls].s2*=m*m;
o[rs].s2*=m*m;
o[ls].s1*=m;
o[rs].s1*=m;
o[i].mul=1;
}
ll ln=o[ls].r-o[ls].l+1;
ll rn=o[rs].r-o[rs].l+1;
if(o[i].sum){
o[ls].sum+=s;
o[rs].sum+=s;
o[ls].s2+=2*o[ls].s1*s+ln*s*s;
o[rs].s2+=2*o[rs].s1*s+rn*s*s;
o[ls].s1+=ln*s;
o[rs].s1+=rn*s;
o[i].sum=0;
}
}
void build(ll i,ll L,ll R){ //initialization
o[i].l=L;o[i].r=R;
o[i].sum=0;
o[i].mul=1;
if(L==R){
o[i].s1=a[L];
o[i].s2=a[L]*a[L];
return;
}
ll mid=L+R>>1;
build(ls,L,mid);
build(rs,mid+1,R);
pushup(i);
}
ll Ask(ll i,ll L,ll R,ll op){ //query interval
if(R<o[i].l||L>o[i].r)return 0;
if(L<=o[i].l&&o[i].r<=R){
if(op==1){
return o[i].s1;
}else{
return o[i].s2;
}
}
ll ans=0;
pushdown(i);
return ans;
}
void mul(ll i,ll L,ll R,ll d){ //Modify the interval
ll l=o[i].l,r=o[i].r;
if(R<l||L>r)return;
if(L<=l&&r<=R){
o[i].s1*=d;
o[i].s2*=d*d;
o[i].mul*=d;
o[i].sum*=d;
return;
}
pushdown(i);
mul(ls,L,R,d);
mul(rs,L,R,d);
pushup(i);
}
void add(ll i,ll L,ll R,ll d){ //Modify the interval
ll l=o[i].l,r=o[i].r;
if(R<l||L>r)return;
if(L<=l&&r<=R){
o[i].s2+=2*o[i].s1*d+(r-l+1)*d*d;
o[i].s1+=(r-l+1)*d;
o[i].sum+=d;
return;
}
pushdown(i);
pushup(i);
}
int main(){
n=R();m=R();
for(ll i=1;i<=n;++i){
a[i]=R();
}
build(1,1,n);
while(m--){
ll op=R();
ll l,r,x;
switch(op){
case 1:{
l=R();r=R();
break;
}
case 2:{
l=R();r=R();
break;
}
case 3:{
l=R();r=R();x=R();
mul(1,l,r,x);
break;
}
case 4:{
l=R();r=R();x=R();
break;
}
}
}
return 0;
}

```

### E. Segment tree

#### Topic meaning:

Board questions plus a lost answer

1 l r v, add v to all numbers in the range a[l] to a[r].

2 l r v, all numbers in the interval a[l] to a[r] are all multiplied by v.

3 l r, calculate the sum of the product of two pairs of numbers between the interval a[l] and a[r] (for example, the sum of the products between 2, 3, 4, and 5 is 2 * 3+2 * 4+2 * 5+3 * 4+3 * 5+4 * 5)

Only need to maintain interval sum sum and square sum pf, you can

The inverse element needs to be used. Since the modulus is a prime number, Fermat's little theorem is directly used.

#### Code:

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll R(){ll a=0,b=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')b=-1;c=getchar();}while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}return a*b;}
const ll MAXN=100010;
#define ls i<<1
#define rs i<<1|1
ll a[MAXN],n,m,p;
struct Tree{
ll l,r,sum,pf;
}o[MAXN<<2];
ll KSM(ll a,ll b){ 		//Fast exponentiation, computes a^b
ll ans=1;
while(b){
if(b&1)ans=(__int128)ans*a%p; 	//if(b%2==1)
a=(__int128)a*a%p;
b>>=1;			//This is equivalent to power=power/2
}
return ans;
}
void pushup(ll i){
o[i].sum=(o[ls].sum+o[rs].sum)%p;
o[i].pf=(o[ls].pf+o[rs].pf)%p;
}
void deal_add(ll i,ll d){ //lazy tag handling
ll r=o[i].r,l=o[i].l;
o[i].pf=(o[i].pf+2*o[i].sum%p*d%p+d*d%p*(r-l+1)%p)%p;
o[i].sum=(o[i].sum+(r-l+1)*d%p)%p;
}
void deal_mul(ll i,ll d){ //lazy tag handling
ll r=o[i].r,l=o[i].l;
o[i].pf=o[i].pf*d%p*d%p;
o[i].sum=o[i].sum*d%p;
o[i].mul=o[i].mul*d%p;
}
void pushdown(ll i){ //mark down
ll ln=o[ls].r-o[ls].l+1;
ll rn=o[rs].r-o[rs].l+1;
if(m!=1){
deal_mul(ls,m);
deal_mul(rs,m);
o[i].mul=1;
}
if(s){
}
}
void build(ll i,ll L,ll R){ //initialization
o[i].l=L;o[i].r=R;
o[i].mul=1;
if(L==R){
o[i].sum=a[L]%p; //Leaf node information
o[i].pf=a[L]*a[L]%p;
return;
}
ll mid=L+R>>1;
build(ls,L,mid);
build(rs,mid+1,R);
pushup(i);
}
ll Ask(ll i,ll L,ll R,ll op){ //query interval
ll l=o[i].l,r=o[i].r;
if(R<l||L>r)return 0;
if(L<=l&&r<=R){
if(op==1)return o[i].sum;
else return o[i].pf;
}
ll ans=0;
pushdown(i);
return ans%p;
}
void Add(ll i,ll L,ll R,ll d){ //Modify the interval
ll l=o[i].l,r=o[i].r;
if(R<l||L>r)return;
if(L<=l&&r<=R){
return;
}
pushdown(i);
pushup(i);
}
void Mul(ll i,ll L,ll R,ll d){ //Modify the interval
ll l=o[i].l,r=o[i].r;
if(R<l||L>r)return;
if(L<=l&&r<=R){
deal_mul(i,d);
return;
}
pushdown(i);
Mul(ls,L,R,d);
Mul(rs,L,R,d);
pushup(i);
}
int main(){
// freopen("R.txt","r",stdin);
ll T=R();
while(T--){
n=R();m=R();p=R();
for(ll i=1;i<=n;++i) a[i]=R();
build(1,1,n);
ll l,r,v;
for(ll i=1;i<=m;++i){
ll op=R();
switch(op){
case 1:{
l=R();r=R();v=R();
break;
}
case 2:{
l=R();r=R();v=R();
Mul(1,l,r,v);
break;
}
case 3:{
l=R();r=R();
printf("%lld\n",((sum*sum%p-mull+p)%p*KSM(2,p-2)%p+p)%p);
break;
}
}
}
}
return 0;
}
```
```            l=R();r=R();v=R();
break;
}
case 2:{
l=R();r=R();v=R();
Mul(1,l,r,v);
break;
}
case 3:{
l=R();r=R();