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
answer:
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);
}
void Add(int x,int d){
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]
Add(i+1,-a[i]);
}
}
int last;
bool check(int now){
if(now>last){
for(int i=last+1;i<=now;++i){
Add(q[i].l,-q[i].d);
Add(q[i].r+1,q[i].d);
}
}else if(last>now){
for(int i=last;i>=now+1;--i){
Add(q[i].l,q[i].d);
Add(q[i].r+1,-q[i].d);
}
}
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
answer:
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);
}
void Add(int x,int d){
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){
if(la[a[i]])Add(la[a[i]],-1);
Add(i,1);
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]
answer:
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];
int a[MAXN],head[MAXN],Next[MAXN],ans[MAXN];
struct node{
int l,r,id;
}q[MAXN];
bool cmp(node a,node b){
return a.l<b.l;
}
void add(int x,int d){
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){
Next[i]=head[a[i]];
head[a[i]]=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){
int t=Next[head[i]];
if(t){
add(t,1);
}
}
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){
add(t,-1);
if(Next[t]){
add(Next[t],1);
}
}
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]
answer:
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);
ans+=Ask(i<<1,L,R,op);
ans+=Ask(i<<1|1,L,R,op);
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);
add(ls,L,R,d);
add(rs,L,R,d);
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();
printf("%lld\n",Ask(1,l,r,1));
break;
}
case 2:{
l=R();r=R();
printf("%lld\n",Ask(1,l,r,2));
break;
}
case 3:{
l=R();r=R();x=R();
mul(1,l,r,x);
break;
}
case 4:{
l=R();r=R();x=R();
add(1,l,r,x);
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)
answer:
Only need to maintain interval sum sum and square sum pf, you can
The final answer is (sum*sum-pf)/2
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;
ll add,mul; //lazy tag
}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;
o[i].add=(d+o[i].add)%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;
o[i].add=o[i].add*d%p;
}
void pushdown(ll i){ //mark down
ll s=o[i].add,m=o[i].mul;
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){
deal_add(ls,s);
deal_add(rs,s);
o[i].add=0;
}
}
void build(ll i,ll L,ll R){ //initialization
o[i].l=L;o[i].r=R;
o[i].add=0;
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);
ans+=Ask(ls,L,R,op);
ans+=Ask(rs,L,R,op);
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){
deal_add(i,d);
return;
}
pushdown(i);
Add(ls,L,R,d);
Add(rs,L,R,d);
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();
Add(1,l,r,v);
break;
}
case 2:{
l=R();r=R();v=R();
Mul(1,l,r,v);
break;
}
case 3:{
l=R();r=R();
ll sum=Ask(1,l,r,1);
ll mull=Ask(1,l,r,2);
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();
Add(1,l,r,v);
break;
}
case 2:{
l=R();r=R();v=R();
Mul(1,l,r,v);
break;
}
case 3:{
l=R();r=R();
ll sum=Ask(1,l,r,1);
ll mull=Ask(1,l,r,2);
printf("%lld\n",((sum*sum%p-mull+p)%p*KSM(2,p-2)%p+p)%p);
break;
}
}
}
}
return 0;
}