UVA 1493 DRAW A MASS
8758 ワード
1つ目は、線分ツリーのバージョンを直接上書きするだけです.
2つ目は、キャッシュされた後、逆順序で上書きされ、シェーディングされていない点が必要であればシェーディングされ、類似したステータス圧縮関数を使用して、変更された点の次の上書きされていない点を求めます.
次のプログラムの入力は掛けましたが、まだ掛けないで走るのが速くて、何も言いません.
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int n,m;
const int N = 211;
const int M = 51111;
int color[N][M<<2];
void build(int l,int r,int rt,int i){
color[i][rt] = 0;
if(l==r) return ;
int m = (l+r)>>1;
build(lson,i);
build(rson,i);
}
void push_down(int rt,int i){
if(color[i][rt]){
color[i][rt<<1]=color[i][rt<<1|1]=color[i][rt];
color[i][rt] = 0;
}
}
void update(int l,int r,int rt,int L,int R,int val,int i){
if(L<=l&&r<=R){
color[i][rt] = val;
return ;
}
push_down(rt,i);
int m = (l+r)>>1;
if(L<=m) update(lson,L,R,val,i);
if(R >m) update(rson,L,R,val,i);
}
int query(int l,int r,int rt,int posi,int i){
if(color[i][rt]||l==r){
return color[i][rt];
}
int m = (l+r)>>1;
if(posi<=m) return query(lson,posi,i);
return query(rson,posi,i);
}
int xc, yc, r, c, l , w;
//xc, yc, r, c;
void circle(int i,int& L,int& R){
int te = r*r - (i-xc)*(i-xc);
if(te<0||i<xc-r||i>xc+r){
L = 1; R = 0; return ;
}
te = floor(sqrt(te*1.0));
L = max(yc-te,1);
R = min(yc+te,m);
// printf("%d --> %d %d
",i,L,R);
}
//xc, yc, r, c£»
void diamond(int i,int& L,int& R){
int te = r - abs(i-xc);
if(te<0){
L = 1; R = 0; return ;
}
L = max(yc-te,1);
R = min(yc+te,m);
}
//xc, yc, l, w, c,
void rectangle(int i,int& L,int& R){
if(i<xc||i>xc+l-1) {
L = 1; R = 0;
return ;
}
L = ceil(max(yc*1.0,1.0));
R = floor(min(yc+w-1.0,m*1.0));
}
//xc, yc, w, c
void triangle(int i,int& L,int& R){
if(i<xc || i >= xc +(w+1)/2){
L= 1; R= 0; return ;
}
int dis=(w-1)/2-(i-xc);
L = max(yc-dis,1);
R = min(yc+dis,m);
}
int main()
{
int Q;
char cmd[100];
while(scanf("%d %d %d",&n,&m,&Q)==3){
for(int i=1;i<=n;i++) build(1,m,1,i);
while(Q--){
scanf("%s",cmd);
if(cmd[0]=='C'){
scanf("%d %d %d %d",&xc, &yc, &r, &c);
xc++; yc++;
for(int i=1;i<=n;i++){
int L,R;
circle(i,L,R);
if(L <= R){
update(1,m,1,L,R,c,i);
}
}
}
else if(cmd[0]=='D'){
scanf("%d %d %d %d",&xc, &yc, &r, &c);
xc++; yc++;
for(int i=1;i<=n;i++){
int L,R;
diamond(i,L,R);
if(L <= R){
update(1,m,1,L,R,c,i);
}
}
}
else if(cmd[0]=='T'){
scanf("%d %d %d %d",&xc, &yc, &w, &c);
xc++; yc++;
for(int i=1;i<=n;i++){
int L,R;
triangle(i,L,R);
if(L <= R){
update(1,m,1,L,R,c,i);
}
}
}
else {
scanf("%d %d %d %d %d",&xc, &yc,&l, &w, &c);
xc++; yc++;
for(int i=1;i<=n;i++){
int L,R;
rectangle(i,L,R);
if(L <= R){
update(1,m,1,L,R,c,i);
}
}
}
}
//void show(); show();
int cnt[10]={0};
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cnt[query(1,m,1,j,i)]++;
for(int i=1;i<=9;i++) {
if(i>1) printf(" ");
printf("%d",cnt[i]);
}
printf("
");
}
return 0;
}
void show(){
printf("*****************
");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d",query(1,m,1,j,i));
}
printf("
");
}
}2つ目は、キャッシュされた後、逆順序で上書きされ、シェーディングされていない点が必要であればシェーディングされ、類似したステータス圧縮関数を使用して、変更された点の次の上書きされていない点を求めます.
次のプログラムの入力は掛けましたが、まだ掛けないで走るのが速くて、何も言いません.
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int n,m;
const int N = 211;
const int M = 51111;
int color[N][M],jump[N][M],cnt[10];
int xc, yc, r, c, l , w;
int find(int st,int i){
if(!color[i][jump[i][st]]) return jump[i][st];
return jump[i][st] = find(jump[i][st],i);
}
void update(int st,int ed,int i){
for(int j=st;j<=ed;){
if(!color[i][j]) {
color[i][j] = 1;
cnt[c]++;
}
j=find(j,i);
}
}
template <class T>
inline bool scan_d(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
struct node{
char cmd;
int data[10];
}cun[M];
void read_input(int i){
char str[100];
scanf("%s",str);
cun[i].cmd=str[0];
scan_d(cun[i].data[0]);
scan_d(cun[i].data[1]);
scan_d(cun[i].data[2]);
scan_d(cun[i].data[3]);
if(str[0]=='R')
scan_d(cun[i].data[4]);
}
//xc, yc, r, c;
void circle(int i,int& L,int& R){
int te = r*r - (i-xc)*(i-xc);
if(te<0||i<xc-r||i>xc+r){
L = 1; R = 0; return ;
}
te = floor(sqrt(te*1.0));
L = max(yc-te,1);
R = min(yc+te,m);
// printf("%d --> %d %d
",i,L,R);
}
//xc, yc, r, c£»
void diamond(int i,int& L,int& R){
int te = r - abs(i-xc);
if(te<0){
L = 1; R = 0; return ;
}
L = max(yc-te,1);
R = min(yc+te,m);
}
//xc, yc, l, w, c,
void rectangle(int i,int& L,int& R){
if(i<xc||i>xc+l-1) {
L = 1; R = 0;
return ;
}
L = ceil(max(yc*1.0,1.0));
R = floor(min(yc+w-1.0,m*1.0));
}
//xc, yc, w, c
void triangle(int i,int& L,int& R){
if(i<xc || i >= xc +(w+1)/2){
L= 1; R= 0; return ;
}
int dis=(w-1)/2-(i-xc);
L = max(yc-dis,1);
R = min(yc+dis,m);
}
int main()
{
int Q;
char cmd[100];
while(scanf("%d %d %d",&n,&m,&Q)==3){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
color[i][j] = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m+1;j++)
jump[i][j]=j+1;
}
for(int i=1;i<=9;i++) cnt[i] = 0;
for(int i=1;i<=Q;i++) read_input(i);
for(int g=Q;g>=1;g--){
if(cun[g].cmd=='C'){
xc = cun[g].data[0];
yc = cun[g].data[1];
r = cun[g].data[2];
c = cun[g].data[3];
xc++; yc++;
for(int i=1;i<=n;i++){
int L,R;
circle(i,L,R);
if(L <= R){
update(L,R,i);
}
}
}
else if(cun[g].cmd=='D'){
xc = cun[g].data[0];
yc = cun[g].data[1];
r = cun[g].data[2];
c = cun[g].data[3];
xc++; yc++;
for(int i=1;i<=n;i++){
int L,R;
diamond(i,L,R);
if(L <= R){
// printf("%d %d
",L,R);
update(L,R,i);
}
}
}
else if(cun[g].cmd=='T'){
xc = cun[g].data[0];
yc = cun[g].data[1];
w = cun[g].data[2];
c = cun[g].data[3];
xc++; yc++;
for(int i=1;i<=n;i++){
int L,R;
triangle(i,L,R);
if(L <= R){
update(L,R,i);
}
}
}
else {
xc = cun[g].data[0];
yc = cun[g].data[1];
l = cun[g].data[2];
w = cun[g].data[3];
c = cun[g].data[4];
xc++; yc++;
for(int i=1;i<=n;i++){
int L,R;
rectangle(i,L,R);
if(L <= R){
update(L,R,i);
}
}
}
}
for(int i=1;i<=9;i++) {
if(i>1) printf(" ");
printf("%d",cnt[i]);
}
printf("
");
}
return 0;
}