记录编号 | 440475 | 评测结果 | AAAAAAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | 1316.数列操作B | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 3.463 s | ||
提交时间 | 2017-08-23 10:15:08 | 内存使用 | 2.61 MiB | ||
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <queue> #include <stack> #include <map> #include <set> #include <list> #include <vector> #include <ctime> #include <iterator> #include <functional> #define pritnf printf #define scafn scanf #define For(i,j,k) for(int i=(j);i<=(k);(i)++) using namespace std; typedef long long LL; typedef unsigned int Uint; const int INF=0x7ffffff; //==============struct declaration============== const int MAXN=100100; int sum[MAXN*3],addv[MAXN*3]; #define y1 y int y1,y2,k,v,n,q; string cmd; //==============function declaration============ void add(int o,int l,int r); int query(int o,int l,int r,int add); void maintain(int o,int l,int r); //==============main code======================= int main() { string FileName="shulieb";//程序名 string FloderName="COGS";//文件夹名 freopen((FileName+".in").c_str(),"r",stdin); freopen((FileName+".out").c_str(),"w",stdout); #ifdef DEBUG system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str()); clock_t Start_Time=clock(); #endif ios::sync_with_stdio(false); cin>>n; For(i,1,n){ cin>>v; y1=y2=i; add(1,1,n); } cin>>q; For(i,1,q){ cin>>cmd; if (cmd[0]=='A'){ cin>>y1>>y2>>v; add(1,1,n); } else if (cmd[0]=='Q'){ cin>>k; cout<<query(1,1,n,0)<<endl; } } #ifdef DEBUG clock_t End_Time=clock(); printf("\n\nTime Used: %.4lf Ms\n",double(End_Time-Start_Time)/CLOCKS_PER_SEC); #endif return 0; } //================fuction code==================== void add(int o,int l,int r) { int lc=o*2,rc=o*2+1,m=(l+r)>>1; if (y1<=l&&r<=y2){ sum[o]+=(r-l+1)*v; addv[o]+=v; return; } if (m>=y1) add(lc,l,m); if (m<y2) add(rc,m+1,r); maintain(o,l,r); } int query(int o,int l,int r,int add) { int lc=o*2,rc=o*2+1,m=(l+r)>>1; if (l==r) return add+sum[o]; int res=0; if (m>=k) return query(lc,l,m,add+addv[o]); if(m<k) return query(rc,m+1,r,add+addv[o]); } void maintain(int o,int l,int r) { int lc=o*2,rc=o*2+1,m=(l+r)>>1; if (l!=r) sum[o]=sum[lc]+sum[rc]+addv[o]*(r-l+1); }