pengbonan @ 2024-08-14 10:55:10
#include<bits/stdc++.h>
#define int long long
#define inf LONG_LONG_MAX
#define endl '\n'
#define ls(t) (t<<1)
#define rs(t) (t<<1|1)
using namespace std;
int n,q,x,l,r,w,c,lasl,lasr,lasc,sum,laz[4100010];
char op,lastop;
struct N{
int mx,mi;
}tr[4100100];
inline int read(){
int x=1,sum=0;
char ch;
ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
x=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
sum=(sum<<3)+(sum<<1)+ch-'0';
ch=getchar();
}
return x*sum;
}
inline void pushup(int p){
tr[p].mx=max(tr[ls(p)].mx,tr[rs(p)].mx);
tr[p].mi=min(tr[ls(p)].mi,tr[rs(p)].mi);
}
inline void pushdown(int p){
if(laz[p]!=0){
laz[ls(p)]+=laz[p];
laz[rs(p)]+=laz[p];
tr[ls(p)].mx+=laz[p];
tr[rs(p)].mx+=laz[p];
tr[ls(p)].mi+=laz[p];
tr[rs(p)].mi+=laz[p];
laz[p]=0;
}
}
inline void update(int pl,int pr,int l,int r,int w,int p){
if(l<=pl&&pr<=r){
tr[p].mx+=w;
tr[p].mi+=w;
laz[p]+=w;
return;
}
pushdown(p);
int mid=pl+pr>>1;
if(l<=mid)update(pl,mid,l,r,w,ls(p));
if(r>mid)update(mid+1,pr,l,r,w,rs(p));
pushup(p);
}
inline int query(int pl,int pr,int l,int r,int c,int p){
if(l<=pl&&pr<=r){
if(c<=tr[p].mi){
return (pr-pl+1);
}
if(c>tr[p].mx){
return 0;
}
}
pushdown(p);
int mid=pl+pr>>1,ans=0;
if(l<=mid)ans+=query(pl,mid,l,r,c,ls(p));
if(r>mid)ans+=query(mid+1,pr,l,r,c,rs(p));
pushup(p);
return ans;
}
inline void build(int l,int r,int p){
if(l==r){
x=read();
tr[p].mx=x;
tr[p].mi=x;
return ;
}
int mid=l+r>>1;
build(l,mid,ls(p));
build(mid+1,r,rs(p));
pushup(p);
}
signed main(){
n=read();
q=read();
build(1,n,1);
for(int i=1;i<=q;i++){
cin>>op;
l=read();
r=read();
w=read();
if(lastop==op&&op=='A'&&lasl==l&&lasr==r&&lasc==w){
cout<<sum<<endl;
continue;
}
if(op=='M'){
update(1,n,l,r,w,1);
}else{
sum=query(1,n,l,r,w,1);
cout<<sum<<endl;
}
lastop=op;
lasl=l;
lasr=r;
lasc=w;
}
return 0;
}同学用线段树乱搞过了，求hack
by pengbonan @ 2024-08-14 10:57:26
代码参考了 this hack数据的生成方式，使用
if(lastop==op&&op=='A'&&lasl==l&&lasr==r&&lasc==w){
cout<<sum<<endl;
continue;
}特判过了，而且跑的飞快
by xiaosuan @ 2024-08-15 11:13:49
这里有一个 hack 数据生成器，你可以试试
输入 1000000 1500 任意不带后缀文件名 即可把你的代码卡爆
#include <bits/stdc++.h>
namespace xiaosuan {
using std::cin;
using std::fstream;
using std::string;
int main() {
int n;
int round;
string filename;
cin >> n >> round >> filename;
fstream inp_file, oup_file;
inp_file.open(filename + ".in", std::ios::out);
oup_file.open(filename + ".out", std::ios::out);
inp_file << n << " " << round * 2 << '\n';
for (int i = 0; i < n; ++i) {
inp_file << (i & 1 ? 2 : 0) << ' ';
}
inp_file << '\n';
for (int i = 0; i < round; ++i) {
inp_file << "M 1 " << n << " 1 \n";
inp_file << "A 1 " << n << " " << (i + 2) << " \n";
oup_file << n / 2 << '\n';
}
inp_file.close();
oup_file.close();
return 0;
}
}
int main() {
return xiaosuan::main();
}by pengbonan @ 2024-08-15 11:22:32
@Maxmilite 请求添加 hack 数据