[洛谷P3948]数据结构
生活随笔
收集整理的這篇文章主要介紹了
[洛谷P3948]数据结构
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目大意：有n個數，opt個操作，并給你md、min、max。
每種操作有以下兩種：1.給一段區間加一個固定值。2.詢問一段區間內滿足$min\leq T*i\ mod\ md\leq max$（T是當前的數，i是當前數的下標）的數的個數。
在這opt個操作里，詢問不超過1000個。
這之后還有final（$<10^7$）個詢問（同上面的詢問），保證這些詢問中間沒有修改操作。
要你實現這些操作。
解題思路：一開始被這些巨大的數據唬住了，經過思考看了標程后突然發現并不是很難。
對于區間和操作，很容易想到差分解決，但中間還有詢問操作，怎么辦？
題目說中間最多1000個詢問，而n最大才80000，對于每一個詢問，都掃描一遍差分數組的話，不考慮常數則要執行大約80000000次操作。
但標程告訴我這樣是可以卡過去的（洛谷神評測機）。
再來考慮后面的詢問，由于沒有了修改操作，我們可以維護一個前綴和，來實現$O(1)$詢問。
然后就玄學地卡了過去。
C++ Code：
#include<cstdio>
#include<cctype>
#include<cstring>
#define ll long long
int n,opt,mod,min,max,l,r,b[80003];
ll a[80003];
char c;
inline int readint(){
char c=getchar();
bool b=false;
for(;!isdigit(c);c=getchar())b=c=='-';
int d=0;
for(;isdigit(c);c=getchar())
d=(d<<3)+(d<<1)+(c^'0');
return b?-d:d;
}
inline void putint(int p){
if(p==0){
putchar('0');
putchar('\n');
return;
}
int w=1;
while(w<=p)w*=10;w/=10;
while(w){
putchar(p/w+'0');
p%=w;
w/=10;
}
putchar('\n');
}
int main(){
n=readint(),opt=readint(),mod=readint(),min=readint(),max=readint();
memset(a,0,sizeof a);
while(opt--){
for(c=getchar();!isalpha(c);c=getchar());
l=readint(),r=readint();
if(c=='A'){
int num=readint();
a[l]+=num,a[r+1]-=num;
}else{
int cnt=0;
ll sum=0;
for(int i=1;i<=r;++i){
sum+=a[i];
if(i>=l)cnt+=(int)(sum%mod*i%mod>=min&&sum%mod*i%mod<=max);
}
putint(cnt);
}
}
b[0]=0;
ll sum=0;
for(int i=1;i<=n;++i){
sum+=a[i];
b[i]=b[i-1]+(int)(sum%mod*i%mod>=min&&sum%mod*i%mod<=max);
}
for(int final=readint();final--;){
l=readint(),r=readint();
putint(b[r]-b[l-1]);
}
return 0;
}
總結
以上是生活随笔為你收集整理的[洛谷P3948]数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 超声波流量计精度比较的几个原因
- 下一篇： 21-8 数据检索2 top和disti